Buzz is a game where people count up from $1$ but skip multiples of $7$ and numbers that contain $7$.

R and J think Buzz is too easy for them so they make it stronger. Now any number that is a multiple of some number that contains $7$ must be skipped.

Formally, let $p(x)$ be $1$ if $x$ contains $7$ in base $10$ and $0$ otherwise. A positive integer $x$ must be skipped when $x=yz$ for some positive integers $y$ and $z$ such that $p(y)=1$.

For example, if R says $6$, because $7$ is skipped, J should say $8$ after $6$. If R says $33$, because $34=17\times 2$ and $35=7\times 5$, J should say $36$ after $33$. If R says $69$, because all numbers from $70$ to $79$ contain $7$, J should say $80$ after $69$.

Input Specification

The first line contains a positive integer $T$ representing the number of test cases.

Each of the next $T$ lines contains a positive integer $x$ said by R.

Output Specification

Output one line for each test case.

If R says a number that should be skipped, output -1. Otherwise output the number J should say after R.

Sample Input 1

4
6
33
69
300

Sample Output 1

8
36
80
-1

Sample 1 Explanation

The first 3 test cases are explained in the statement. For the 4th test case, $300=75\times 4$. Because $75$ contains $7$, $300$ should be skipped.

Sample Input 2

5
90
99
106
114
169

Sample Output 2

92
100
109
-1
180

Additional Samples

Additional samples can be found here.

Constraints

For 10% of the test cases, $T\le 10$, $x\le 100$.

For 30% of the test cases, $T\le 100$, $x\le 1000$.

For 50% of the test cases, $T\le 1000$, $x\le 10000$.

For 70% of the test cases, $T\le 10000$, $x\le {10}^5$.

For 100% of the test cases, $T\le 2\times {10}^5$, $x\le {10}^7$.