Problem Description

LNC likes numbers whose product of all digits in base $k$ is a divisor of the number itself. He calls such numbers LNC numbers. For example:

When $k = 10$, $y = (36)_{10}$ is an LNC number because $(3 \times 6) \mid 36$.

When $k = 4$, $y = (12)_4$ is an LNC number because after converting to decimal, $(12)_4 = (6)_{10}$, and $(1 \times 2) \mid 6$.

When $k = 2$, $y = (1101)_2$ is not an LNC number because after converting to decimal, $(1101)_2 = (13)_{10}$, and $0$ is not a divisor of $13$.

LNC is playing a game with LJJ. LJJ gives $x$ chess pieces, and then LNC chooses an integer $k$ ($k \geq 2$). After that, they take turns removing some chess pieces, and the number of pieces removed each time must be an LNC number in base $k$. LNC moves first, and whoever takes the last pieces wins. Both players are extremely smart, so they will both play with the best strategy.

LJJ thinks this game is unfair. They played a total of $T$ games. For each given $x$, he wants to know the smallest $k$ such that LNC, as the first player, is guaranteed to win.

Input Format

The first line contains a positive integer $T$ ($1 \le T \le 1 \times 10^2$), indicating the number of test cases.

The next $T$ lines each contain a positive integer $x$ ($3 \le x \le 10^{18}$), representing the number $x$ given by LJJ.

Output Format

Output $T$ lines, each containing a positive integer $k$, the smallest $k$ such that for that query, LNC (the first player) is guaranteed to win.

3
9
5
10

2
2
3

Hint

When $x=5$, LNC can choose $k=2$. $x=(5)_{10}=(101)_2$.

LNC first removes $(11)_2$. Then $x=(10)_2$. LJJ can only remove $(1)_2$, and then LNC removes the last $(1)_2$ and wins.

Also, since $k=2$ cannot be any smaller, the final answer is $k=2$.

Translated by ChatGPT 5