Statement

What is the smallest base larger than 2 in which the integer \(n\) contains only the digits 0 and 1?

Input format

The first line of each input file contains the number \(t\) of test cases.

Each of the following \(t\) lines contains a single integer \(n\) (in base 10).

Output format

For each test case output a single line with a single number.

If \(n\) cannot be represented using 1s and 0s in any base larger than 2, output \(-1\).

Otherwise, output an integer \(b\): the smallest base larger than 2 in which \(n\)’s representation contains only 1s and 0s.

Subproblem B1 (17 points, public)

Input file: B1.in

Constraints: \(1 \leq t \leq 10^3\) and in each test \(1 \leq n \leq 10^3\).

Subproblem B2 (30 points, public)

Input file: B2.in

Constraints: \(1 \leq t \leq 10^4\) and in each test \(1 \leq n \leq 10^9\).

Subproblem B3 (53 points, secret)

Input file: B3.in

Constraints: \(1 \leq t \leq 10^4\) and in each test \(1 \leq n \leq 10^{18}\).

Example

3
20
273
1332

4
3
6

273 in base 3 is 101010.