## NOIP '21 P1 - Saying Numbers

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

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 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, , .