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 1\,000~.

For 50% of the test cases, ~T \le 1\,000~, ~x \le 10\,000~.

For 70% of the test cases, ~T \le 10\,000~, ~x \le 10^5~.

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