- All Contests
- ProjectEuler+
- Project Euler #200: Find the 200th prime-proof sqube containing the contiguous sub-string "200"

# Project Euler #200: Find the 200th prime-proof sqube containing the contiguous sub-string "200"

# Project Euler #200: Find the 200th prime-proof sqube containing the contiguous sub-string "200"

_{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
```