The "number-calling" game is a widely popular casual game. Participants take turns calling out numbers in a specific order. However, if the next number to be called is a multiple of 7, or if its decimal representation contains the digit 7, that number must be skipped; otherwise, the player loses the game.

On a beautiful afternoon, little r and little z, who had just finished the $SPC20nn$ competition, were bored and started playing this number-calling game. While it is relatively easy to calculate when only two people are playing, they played for a long time without a winner. At this moment, little z had a flash of inspiration and decided to strengthen the game: any number that contains the digit 7 in its decimal representation, as well as all of its multiples, cannot be called out!

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 called out if and only if there exist positive integers $y$ and $z$ such that $x = yz$ and $p(y) = 1$.

For example, if little r calls out 6, since 7 cannot be called, little z needs to call out 8 next. If little r calls out 33, since $34 = 17 \times 2$ and $35 = 7 \times 5$ cannot be called, little z needs to call out 36 next. If little r calls out 69, since all numbers from 70 to 79 contain the digit 7, little z must call out 80 next.

Now, little r has just called out $x$, and little z wants to quickly calculate what his next number should be. However, he soon realizes that this game is much harder to calculate than the original version, so he needs your help. Of course, if the $x$ called out by little r is itself a number that cannot be called, you must also react quickly to indicate that little r has lost.

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

Input

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

The next $T$ lines each contain a single positive integer $x$, representing the number called out by little r in that turn.

Output

Output $T$ lines, each containing an integer. If the number $x$ called out by little r cannot be called, output $-1$; otherwise, output the number that little z should call out next.

Examples

Input 1

4
6
33
69
300

Output 1

8
36
80
-1

Note 1

The first 3 queries of this example are already explained in the problem description. For the 4th query, since $300 = 75 \times 4$ and 75 contains the digit 7, little r has lost the game.

Input 2

5
90
99
106
114
169

Output 2

92
100
109
-1
180

Examples 3 and 4

See number/number3.in and number/number3.ans, and number/number4.in and number/number4.ans in the contestant's directory.

Constraints

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