By XI Maratona de Programação IME-USP, 2007 Brazil
John is a very smart sixth grade boy. He likes Maths a lot, and he found out that his teacher is very lazy. At the tests, the teacher asks the kids to circle their answers with a coloured square, and also asks them to make the number's first non-zero digit (right-to-left) specially big, using a pen. John suspected that the teacher used only that digit to grade the question.
The class learned to calculate the factorial of a number, and that is going to be the subject for the next test. John is convinced that he doesn't need to actually write the right number, as long as the first digit (right-to-left) is right. Your task in this problem is to help John calculate, for an integer number n from the input, the first digit (right-to-left) in n! that is different to zero.
The input consists in many instances. The first line for each instance consists in an integer n (1 ≤ n ≤ 1000000).
The input ends with file end.
For each instance, you'll have to print a k instance identifier, where k is the current instance number. At the next line, print the first digit (right-to-left) that is different to zero.
After each instance, print a blank line.
|Sample Input||Sample Output|