Buzz is a game where people count up from but skip multiples of
and numbers that contain
.
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 must be skipped.
Formally, let be
if
contains
in base
and
otherwise. A positive integer
must be skipped when
for some positive integers
and
such that
.
For example, if R says , because
is skipped, J should say
after
. If R says
, because
and
, J should say
after
. If R says
, because all numbers from
to
contain
, J should say
after
.
Input Specification
The first line contains a positive integer representing the number of test cases.
Each of the next lines contains a positive integer
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, . Because
contains
,
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, ,
.
For 30% of the test cases, ,
.
For 50% of the test cases, ,
.
For 70% of the test cases, ,
.
For 100% of the test cases, ,
.
Comments