Problem C: Calcuator

Suppose you have a calculator which has a precision of n decimal digits. The calculator can perform arithmetic on integers containing at most n decimal digits but if some result overflows then it displays only the least significant n digits and ignores the remaining digits. In other words, it computes modulo $10^n$. You enter a positive integer $>$ 1 with at most n decimal digits with no leading zeroes and press the $x^2$ key which computes the square of the number displayed. Magically, the number displayed remains the same. You have to write a program to find the number that was originally entered. If there is more than one such number possible, your program should find them all. Note that the calculator does not display leading zeroes.

Input

The input for this problem will be a sequence of positive integers specifying different values of n $\geq$ 1. The sequence will be terminated by a 0. Assume that the maximum value of n is at most 1000.

Output

The output should consist of all the possible answers (one per line, in increasing order) for each value of n. Each answer should be written on a separate line as a character string, starting with the most significant non-zero digit without any (leading or trailing) spaces. The answers for different values of input n should be written in the same order as specified in the input.

Sample Input

1
2
0

Sample Output

5
6
25
76