L. Chess
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

LNC likes numbers the product of whose digits is a factor of itself under the base of $$$k$$$. He calls these special numbers LNC-number. For example:

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

When $$$k = 4$$$, $$$y = (12)_4$$$ is a LNC-number because $$$(12)_4 = (6)_{10}$$$ while $$$(1 \times 2) \mid 6$$$.

When $$$k = 2$$$, $$$y = (1101)_2$$$ is not a LNC-number because $$$(1101)_2 = (13)_{10}$$$ while $$$0$$$ is not the factor of $$$13$$$.

LNC is playing a game with LJJ in which LJJ gives $$$x$$$ pieces and then LNC chooses an integer $$$k$$$ ($$$k \geq 2$$$). They then alternately take away a number of pieces, requiring that the number of pieces taken should be a LNC-number under the base of $$$k$$$. LNC takes the first move, and the first one who cannot take pieces loses. Both LNC and LJJ are smart enough to choose the optimal strategy.

LJJ feels that this game is unfair. They play $$$T$$$ games. For each $$$x$$$ he gives, he wants to know the smallest $$$k$$$ such that LNC wins first.

Input

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

One positive integer $$$x$$$ ($$$3 \le x \le 10^{18}$$$) per line for each of the next $$$T$$$ lines, representing the number $$$x$$$ given by LJJ.

Output

Output $$$T$$$ lines, each containing a positive integer $$$k$$$, representing the smallest $$$k$$$ for each query that ensures LNC will win.

Example
Input
3
9
5
10
Output
2
2
3
Note

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

LNC takes away $$$(11)_2$$$ first, then $$$x=(10)_2$$$, and LJJ can only take away $$$(1)_2$$$. LNC takes the last $$$(1)_2$$$ and wins.

Since $$$k=2$$$ cannot be smaller, the final answer is $$$k=2$$$.