Problem Description

The counting-off game is a widely known casual game. Everyone in the game takes turns counting in a fixed order. However, if the next number to be spoken is a multiple of $7$, or its decimal representation contains the digit $7$, then this number must be skipped; otherwise, the player loses.

On a sunny afternoon, little r and little z, who had just finished the SPC20nn contest, were bored and started playing this counting-off game. But with only two players, it was still easy to compute, so they played for a long time without deciding a winner. Then little z had an idea and decided to strengthen the game: for any number whose decimal representation contains the digit $7$, none of its multiples are allowed to be spoken.

Formally, let $p(x)$ indicate whether the decimal representation of $x$ contains the digit $7$. If it does, then $p(x) = 1$; otherwise, $p(x) = 0$. Then a positive integer $x$ cannot be spoken if and only if there exist positive integers $y$ and $z$ such that $x = yz$ and $p(y) = 1$.

For example, if little r says $6$, then since $7$ cannot be spoken, little z needs to say $8$ next. If little r says $33$, then since $34 = 17 \times 2$ and $35 = 7 \times 5$ both cannot be spoken, little z needs to say $36$ next. If little r says $69$, then since all numbers from $70 \sim 79$ contain $7$, little z must say $80$ next.

Now little r previously said $x$, and little z wants to quickly compute what number he should say next. But he soon finds that this game is much harder to compute than the original one, so he needs your help. Of course, if the number $x$ said by little r itself is not allowed, you should also quickly realize that little r has lost.

Since little r and little z have been playing for a long time, you also need to answer many questions from little z.

Input Format

The first line contains a positive integer $T$, indicating the number of queries from little z.

The next $T$ lines each contain a positive integer $x$, indicating the number said by little r in this round.

Output Format

Output $T$ lines in total. For each line, output an integer: if the number said by little r in this round is not allowed, output $-1$; otherwise, output the number that little z should say next.

4
6
33
69
300

8
36
80
-1

5
90
99
106
114
169

92
100
109
-1
180

见附件中的 number/number3.in

见附件中的 number/number3.ans

见附件中的 number/number4.in

见附件中的 number/number4.ans

Hint

Sample Explanation #1

The first $3$ queries in this sample have already been explained in the problem description.

For the $4$-th query, since $300 = 75 \times 4$, and $75$ contains the digit $7$, little r loses immediately.

Constraints

For $10\%$ of the testdata, $T \leq 10$, $x \leq 100$.
For $30\%$ of the testdata, $T \leq 100$, $x \leq 1000$.
For $50\%$ of the testdata, $T \leq 1000$, $x \leq 10000$.
For $70\%$ of the testdata, $T \leq 10000$, $x \leq 2 \times {10}^5$.
For $100\%$ of the testdata, $1 \le T \leq 2 \times {10}^5$, $1 \le x \leq {10}^7$.

Translated by ChatGPT 5