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

2

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