# Factorial

1000ms    65536K
72    15
Beginner

Description

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

The input file consists of several positive integers delimited by whitespace and end by zero. (1 < N < 1092)

Output

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.

Sample Input

1
2
3
4
5
6
7
8
0

Sample Output

1
2
6
4
2
2
4
2

Source

Editor

on 2009-12-24 20:55:56