A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

we define here a new prime number called prime of primes number (POP) is a prime number that consist of other prime numbers less than this number.

example:

1013 consist of 101 and 3 and both are primes.

notes:

2003 is not POP because leading zero not allowed.

The POP number must contain more than or equal two primes, and overlapping not allowed.

Input

The first line contains an integer T specifying the number of test cases (T <= 200) followed by T lines, each line contains an integer m number 0 <=m <= 10^27.

Output

For each test case, print a single line containing the first integer greater than or equal to m and is (POP).

Example

Input:
3
10
100
1000
Output:
23
113
1013

time limit has been changed and all solution was rejudged.