Number Conversion

One of the first lessons for computer science students is representing natural numbers in the binary numeral system (base ~2~). This system uses only two digits, ~0~ and ~1~.

In everyday life, we use the decimal system (base ~10~) for convenience, which uses ten digits, from ~0~ to ~9~. Generally, we could use any numbering system. For example, computer scientists often use systems based on ~8~ or ~16~. In a numbering system with base ~K~, ~K~ digits are used with values from ~0~ to ~K - 1~.

Suppose a natural number ~M~ is given, written in the decimal system. To convert it to the corresponding representation in the base ~K~ system, we successively divide ~M~ by ~K~ until we reach a quotient smaller than ~K~. The representation of ~M~ in the base ~K~ system is formed by the final quotient (as the first digit) followed by the remainders of the preceding divisions. For example, for ~M = 122~ and ~K = 8~:

That is, ~122_{10} = 172_8~ (the number ~122~ in the decimal system is equal to ~172~ in the octal system: ~172_8 = 1 \times 8^2 + 7 \times 8 + 2 = 122_{10}~ ). A student made the following observation: by applying the above rule of converting natural numbers to another numbering system, in some cases, all the digits of the number are the same in the new representation. For example, ~63_{10} = 333_4~.

Problem

Write a program in one of the IOI languages which, when given a number ~M~ in its decimal representation, finds the smallest base ~B~ such that in the representation of ~M~ in base ~B~, all the digits are the same.

Input

The input files named numbase.in are text files with the following structure: The first line contains a natural number ~N\;(1 \le N \le 10)~, the number of numbers to follow. ~N~ lines follow, each containing a natural number ~M_k\;( 1 \le M_k \le 10^{12}~ where ~1 \le k \le N~ ).

Output

The output files named numbase.out are text files with the following structure: They contain ~N~ lines, each containing only one integer ~B_k\;( 2 \le B_k~ where ~1 \le k \le N )~. ~B_k~ must be the minimum base so that the representation of the number ~M_k~ has all its digits the same.

Example of Input - Output Files:

STDIN (numbase.in)

5
7
42
63
2
630

STDOUT (numbase.out)

2
4
2
3
29

Scorring:

In ~30~% of the test cases, ~M_k~ will be ~\le~ ~10^3~.
In ~50~% of the test cases, ~M_k~ will be ~\le~ ~10^6~.
In ~75~% of the test cases, ~M_k~ will be ~\le~ ~10^9~.

Attention!: For ~25~% of the test cases, you will need 64-bit integers (long long or int64_t in GNU C/C++, Int64 in Free Pascal).

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 64 MB.