Problem F. Digits product sequence

Problem

Consider a non-negative integer x. Let P(x) be the product of the non-zero digits of x. For example, P(3209) = 3 x 2 x 9 = 54. A digits product sequence of x is defined to be {x, P(x), P(P(x)), ...} until the resultant number has only 1 digit. The length of the sequence is the number of items in it.

For example, the digit product sequence of 987 is {987, 504, 20, 2} and the length of the sequence is 4.

Your task is to find 10 numbers so that their product sequences are of lengths 1, 2, ..., 10 respectively; each number should be the smallest possible one. It is known that all these numbers are less than 1010.

Input

There is no input to your program.

Output

Output 10 numbers, each on a line of itself, so that the i-th number is the smallest number that has digit product sequence of length i.

Sample Input

Sample Output

1
11
...