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 .
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 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 can be found here.
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, , .