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