NOIP '21 P1 - Saying Numbers

View as PDF

Submit solution

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

Problem type

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.


Comments

There are no comments at the moment.