POP2 - play with prime numbers (II)


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

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^18 .

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/POP3/



hide comments
praveen123: 2013-06-20 20:22:44

@abdou 00, Your problems are really awesome :)

abdou_93: 2013-06-06 17:08:45

@Robert Gerbicz.. congratulation you the first one


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