27405번 - Galactic Bonus 다국어

The Parliament of the Galactic Federation, worried about its declining popularity, decided to throw a bone to the citizens of the galaxy. Specifically, the Parliament decided to pay a bonus to all the citizens whose age in years is a round number (years have the same length on all planets thanks to the Standard Galactic Calendar). Naysayers objected that species use different bases in their number systems and therefore “round numbers” are impossible to define. After many deliberations, the Parliament decided that an age A will be considered round if it can be written as 100...100... in any base B (two digits of 1 and zero or more digits of 0). The amount of the bonus is the smallest base B in which the number A is round.

Once the law was enacted, the Parliament needed a quick way to determine the bonuses, so that the citizens could receive the money before the upcoming elections.

Given the number of citizens, N, and the age A_i of every citizen i, help the parliament compute the lowest base in which A_i is a round number.

The input contains an integer number N on the first line, representing the number of citizens in the galaxy. The following N lines contain the integer ages A₁, A₂, ..., A_N, one per line.

The output must contain N lines. Line i must contain a single number, the lowest base in which A_i is a round number.

• 1 ≤ N ≤ 100,000
• 3 ≤ A_i ≤ 2⁶⁴ - 1 for all 1 ≤ i ≤ N

• 36 = 100100₂
• 26 = 101₅
• 80 = 1010000₂
• 56 = 110₇
• 125 = 11₁₂₄

Some numbers are round in multiple bases. For example, 36 is also round in base 3: 36 = 1100₃. However, the answer must be the lowest base.