Problem Description

The Counting Game is a widely popular casual game. In the game, participants take turns counting numbers in a certain order. However, if the next number to be counted is a multiple of $7$ or contains the digit $7$ in its decimal representation, that number must be skipped, or the player loses the game.

On a sunny afternoon, just after the SPC20nn competition, Xiao R and Xiao Z, feeling bored, decided to play this counting game. With only two players, the calculations were relatively straightforward, so they played for a long time without a winner. Xiao Z then had a brilliant idea to enhance the game: any number containing the digit $7$ in its decimal representation, along with all its multiples, cannot be counted!

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

For example, if Xiao R counts $6$, since $7$ cannot be counted, Xiao Z needs to count $8$ next; if Xiao R counts $33$, then since $34 = 17 \times 2$ and $35 = 7 \times 5$ cannot be counted, Xiao Z needs to count $36$ next; if Xiao R counts $69$, since all numbers from $70$ to $79$ contain the digit $7$, Xiao Z needs to count $80$ next.

Now, Xiao R has counted the number $x$, and Xiao Z wants to quickly calculate the next number he should count. However, he soon realizes that this version of the game is much harder to calculate than the original, so he needs your help. Of course, if Xiao R's number $x$ itself cannot be counted, you must quickly realize that Xiao R has lost.

Since Xiao R and Xiao Z have been playing for a long time, you need to answer many questions from Xiao Z.

Input Format

The first line contains a positive integer $T$ representing the number of queries from Xiao Z.

The next $T$ lines each contain a positive integer $x$, representing the number that Xiao R has counted in this round.

Output Format

Output $T$ lines, each containing an integer. If Xiao R's number in this round cannot be counted, output $-1$. Otherwise, output the next number that Xiao Z should count.

Sample Input and Output

Sample Input #1

4
6
33
69
300

Sample Output #1

8
36
80
-1

Sample Input #2

5
90
99
106
114
169

Sample Output #2

92
100
109
-1
180

Sample Input #3

See the attached file number/number3.in

Sample Output #3

See the attached file number/number3.ans

Sample Input #4

See the attached file number/number4.in

Sample Output #4

See the attached file number/number4.ans

Notes/Hints

[Sample Explanation #1]

The first three queries in this sample set are explained in the problem description.

For the fourth query, since $300 = 75 \times 4$ and $75$ contains the digit $7$, Xiao R loses the game immediately.

[Data Range]

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

见题面 Input 部分

见题面 Output 部分