FCTRL4 - Last Non-Zero Digit of Factorials

Tom is fascinated by big numbers. Most of all he likes factorials. First, he computed N! for some small values of N. But factorials were getting longer and longer very quickly and each of them had a long sequence of zeroes at its end. Since he was unable to consider so many digits in his research and he thought that the research on zeroes would be boring, he decided to focus on the last non-zero digit of factorials.

For example 4!=24 so the last non-zero digit is 4. For N=5 we have 5!=120 and the last non-zero digit 2.

Tom needs to know the last non-zero digit of N! for several specific values of N. Help him please.

Input specification

The input file consists of several positive integers (less than 10100) delimited by whitespace.

Output specification

The output file contains the last non-zero digit of N! for each integer N from the input file. Digits should be delimited by whitespace.

Example

Input file:
1
2
3
4
5
6
7
8

Output file:
1
2
6
4
2
2
4
2  

Added by:Fudan University Problem Setters
Date:2007-12-01
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C99 ERL JS-RHINO OBJC SQLITE
Resource:IPSC 1999

hide comments
2010-11-14 18:18:35 Hagen von Eitzen
Since N can be up to 10^100, I assume Debanjan rather means O(log(N)^2). ;)
2010-07-12 17:01:09 sudipto das
@c/c++ users:take input as follows--
while(scanf("%s",N)>0)
{
----//code
}
2010-07-10 07:08:57 Ankit Gupta
my code is running for small values.can someone tell me the output for 5000...
2010-07-07 12:47:20 Tirumarai Selvan
Sorry its O(nk) where k<<n.
2010-07-07 12:45:42 Tirumarai Selvan
I have an O(n) algo but still TLE. I am assuming long long int for N.
2010-06-22 00:23:39 :(){ :|: & };:

It is only possible to get an accepted verdict by an O(N^2) algorithm.
2010-06-19 10:35:33 Shrainik Jain
how does the input end?
2009-12-13 08:38:24 arpit rusia
what is the constraint on the value of a particular integer ??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.