This problem is a programming version of Problem 200 from projecteuler.net
We shall define a sqube to be a number of the form, , where and are distinct primes.
For example, or .
The first five squbes are , , , , and .
Interestingly, is also the first number for which you cannot change any single digit to make a prime; we shall call such numbers, prime-proof. The next prime-proof sqube which contains the contiguous sub-string "200" is . Note that changing a digit may result in appearance of the leading zeroes - in the case with as a number we can change the first digit to , but the resulting number is not a prime number and doesn't change the fact that is prime-proof.
You're given the contiguous sub-string and some queries . For each query, find the -th prime-proof sqube containing the contiguous sub-string .
Input Format
The first line of each file contains which is the sub-string from the problem statement. Next line contains a single integer which is the number of queries per test file. lines follow, each containing the corresponding .
Constraints
- is a string representation of some number between and
- For each query, the answer is less than .
Output Format
Print exactly lines with the answers for the all queries on each.
Sample Input 0
200
2
1
2
Sample Output 0
200
1992008
Sample Input 1
632
3
1
3
2
Sample Output 1
42632
963272
256328