Galactic Bonus

The Parliament of the Galactic Federation is losing popularity, so it decided to pay a bonus to citizens whose age in years is a round number. Years have the same length on all planets thanks to the Standard Galactic Calendar.

Some species use different bases in their number systems, so critics said "round numbers" cannot be defined. After long debate, the Parliament ruled that an age $A$ is round if it can be written as $100\ldots100\ldots$ in some base $B$. That means exactly two digits are 1, and all other digits are 0. The bonus is the smallest base $B$ in which $A$ is round.

Once the law took effect, the Parliament needed a fast way to compute the bonuses. Given the number of citizens $N$ and each citizen's age $A_i$, find the lowest base in which each age is round.

The first line contains an integer $N$, the number of citizens. Each of the next $N$ lines contains one integer age $A_i$.

Print $N$ lines. Line $i$ contains the lowest base in which $A_i$ is a round number.

$1 \le N \le 100{,}000$

$3 \le A_i \le 2^{64} - 1$ for every $i$.

$36 = 100100_2$

$26 = 101_5$

$80 = 1010000_2$

$56 = 110_7$

$125 = 11_{124}$

Some numbers are round in several bases. For example, 36 is also round in base 3, since $36 = 1100_3$. The answer must still be the lowest base, so the answer for 36 is 2.