POP3 - play with prime numbers (III)(hard )

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.


Added by:abdou_93
Date:2013-06-06
Time limit:90s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:owner

hide comments
2013-06-07 15:32:43 abdou_93
@Robert Gerbicz
the time limit has been changed and your old correct code in the worst case runs in 109.52 sec .

Last edit: 2013-06-06 19:06:40
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.