Internet Problem Solving Contest

• Easy input data set – D1
• Hard input data set – D2

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 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