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.

For example: 1013 consist of 101 and 3 and both are primes.

Note: 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 <= 10^4) followed by T lines, each line contains an integer m number 0 <= m <= 10^9.

Output

For each test case print single line contain the first integer greater than or equal to m and is POP.

Example

Input:
3
10
100
1000
Output:
23
113
1013

after solving this you can try http://www.spoj.com/problems/POP2/