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 .
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 .
is a string representation of some number between and
For each query, the answer is less than .
Print exactly lines with the answers for the all queries on each.