Problem H
LCM
Input: standard input
Output: standard output
Time Limit: 2 seconds

All of you know about LCM (Least Common Multiple). For example LCM of 4 and 6 is 12. LCM can also be defined for more than 2 integers. LCM of 2, 3, 5 is 30. In the same way we can define LCM of first N integers. The LCM of first 6 numbers is 60.

As you will see LCM will increase rapidly with N. So we are not interested in the exact value of the LCM but we want to know the last nonzero digit of that. And you have to find that effeciently.

Input

Each line contains one nonzero positive integer which is not greater than 1000000. Last line will contain zero indicating the end of input. This line should not be processed. You will need to process maximum 1000 lines of input.

Output

For each line of input, print in a line the last nonzero digit of LCM of first 1 to N integers. 

Sample Input                              Output for Sample Input

3

5

10

6

6

Problemsetter: Md. Kamruzzaman, Member of Elite Problemsetters’ Panel
Special thanks to: Mohammad Sajjad Hossain

求 1...N的最小公倍數的最後一位非零的數。
這一題假使我們知道 1...N 的最小公倍數就可以知道 1...N+1 的最小公倍數。
如果 N+1 是某一個質數p的次方時，則將 LCM(N)*p = LCM(N+1)。

計算時使用大數乘法會比較保險，不過要隨時將尾數0的去掉，保留幾位自行選擇，不然全部記錄很消耗時間。

#include <stdio.h>
#include <math.h>
char f[1000001];
int apart(int n) {
    int i, sq = (int)sqrt(n);
    int flag = 0;
    for(i = 2; i <= sq; i++) {
        if(n%i == 0) {
            while(n%i == 0)
                n /= i;
            flag = 1;
            break;
        }
    }
    if(flag && n == 1)
        return i;
    if(!flag)
        return n;
    return 0;
}
int bigNum[101] = {2}, tmp[101] = {};
int len = 1;
void mult(int n) {
    int i, j;
    for(i = 0; i <= len; i++)
        tmp[i] = bigNum[i]*n;
    for(i = len+1; i <= len+10; i++)
        tmp[i] = 0;
    for(i = 0; i <= len+10; i++) {
        tmp[i+1] += tmp[i]/10, tmp[i] %= 10;
    }
    j = 0;
    while(tmp[j] == 0)  j++;
    for(i = 0; i <= len+10; i++, j++)
        bigNum[i] = tmp[j];
    len += 10;
    while(!bigNum[len]) len--;
    if(len > 10)    len = 10;
}
int main() {
    f[1] = 1, f[2] = 2;
    int i, j;
    for(i = 3; i <= 1000000; i++) {
        j = apart(i);
        if(j)   mult(j);
        f[i] = bigNum[0];
    }
    while(scanf("%d", &i) == 1 && i)
        printf("%d\n", f[i]);
    return 0;
}