Lost Prime No.s

The BSA (Bytelandian Security Agency) has intercepted several secret keys from the Trojan Kingdom. Each secret key is a prime number. But BSA was only able to retrieve some part of the digits, not all of them!

Johnny's job is to help BSA recover these lost primes, and he has delegated the task to you!

Input

The first line contains a number t (about 15) which is the number of test cases. Then t test cases follow. Each test case is described in a single line containing the patterns of the lost primes (the unknown digits are represented by '?'s.
Each pattern's length is at most 12.

Output

For each test case, print the recovered prime. If there are multiple solutions, print any of them. The recovered prime should have the same number of digits as the corresponding pattern and should contain no leading zeros.
You can assume that there is at least one solution for each test case.

Example

Input:
3
?
?3
1??

Output:
5
23
101