The expression N!, read as "N factorial," denotes the product of the first N positive integers, where N is nonnegative. So, for example,

 N       N!
 0       1
 1       1
 2       2
 3       6
 4      24
 5     120
10 3628800

For this problem, you are to write a program that can compute the last non-zero digit of any factorial for (0 <= N <= 10000). For example, if your program is asked to compute the last nonzero digit of 5!, your program should produce "2" because 5! = 120, and 2 is the last nonzero digit of 120.

Input Format

Input to the program is a series of nonnegative integers not exceeding 10000, each on its own line with no other letters, digits or spaces. For each integer N, you should read the value and compute the last nonzero digit of N!.

Required Output Format

For each integer input, the program should print exactly one line of output. Each line of output should contain the value N, right-justified in columns 1 through 5 with leading blanks, not leading zeroes. Columns 6 - 9 must contain " -> " (space hyphen greater space). Column 10 must contain the single last non-zero digit of N!.

Sample Input

1
2
26
125
3125
9999

Sample Output

    1 -> 1
    2 -> 2
   26 -> 4
  125 -> 8
 3125 -> 2
 9999 -> 8

Judge's Input

1
2
3
4
5
6
7
8
9
10
14
15
24
25
26
124
125
624
625
3124
3125
9999
100
200
501
5001
7029
7501

Judge's Output

    1 -> 1
    2 -> 2
    3 -> 6
    4 -> 4
    5 -> 2
    6 -> 2
    7 -> 4
    8 -> 2
    9 -> 8
   10 -> 8
   14 -> 2
   15 -> 8
   24 -> 6
   25 -> 4
   26 -> 4
  124 -> 4
  125 -> 8
  624 -> 6
  625 -> 6
 3124 -> 4
 3125 -> 2
 9999 -> 8
  100 -> 4
  200 -> 2
  501 -> 4
 5001 -> 2
 7029 -> 4
 7501 -> 6

Solution in C++

#include <iostream.h>
#include <fstream.h>
 
int main()
{
  ifstream in("facts.dat");
  ofstream out("facts.out");
  int n;
 
  while (in >> n)
    {
      long prod = 1;
      for (int i=1; i<=n; ++i)
        {
          long f = i;
          while (f % 5 == 0)
            {
              f/= 5;
              prod /=2;
            }
          prod = (prod % 100000) * f;
        }
      out.width(5);
      out << n << " -> " << (prod%10) << "\n";
    }
}

Comment

A key observation is that multiplying (n-1)! by a multiple of 5 introduces a new zero at the end; more generally, multiplying by a multiple of 5**k introduces k new zeroes at the end.  For n <= 10000, the key numbers are 3125, 6250 and 9375, all multiples of 5 to the fifth.  Before multiplying by one of these numbers, you must have available at least the 6 least significant nonzero digits of the factorial of the previous number.  In testing,
9375! was the test case that gave the judges the most trouble, but that input did not make it into the judge's test data.  Would your program have handled it?