Low Order Zeros

When you compute a large, factorial number, it has a long string of low-order zeros at the end. This makes sense; every time you multiply in something like a $10$ or a $20$, you are sure to pick up another low-order zero. Thus, it’s easy to guess the low-order digit of something like $3\, 249!$. It’s a little harder to guess what the lowest-order non-zero digit will be. Write a program to do that.

Input

Input consists of up to $1\, 000$ test cases, one per line. Each test case is a single positive integer $i \le 10^6$. Input ends with a value of zero.

Output

For each test case, print out the value of the rightmost (lowest-order) non-zero digit of $i!$.

Sample Input 1 Sample Output 1
3
25
492
0
6
4
8