PRIME12 - Fun With Primes

no tags 

A prime number is a number whose only divisors are 1 and itself. A sublinear polynomial-time algorithm has been shown to exist that determines primality or non-primality with certainty, unlike the previous probablistic tests, but it is extremely complicated. There must be an easier way.

In engineering, exact solutions are often not required, only good approximations. Thus, an "Engineer's Prime" of order N is any number that is divisible by none of the first N primes, since the smallest primes are easy to remember: 2, 3, 5, and so on. Note that 1 is not considered a prime in this case.

Given an int N, your program should output the smallest Engineer's Prime of order N that is not prime.

Input

First line contains the number of test cases T <= 100. Following each line contains an integer 1 <= N <= 105

Output

For each line of testcase, output single integer -  smallest Engineer's Prime of order N that is not prime.

Example

Input:

3
265
1835
10000
Output:
2886601
247716121
10971096049

hide comments
John and the cows: 2013-08-15 07:44:56

piece of cake :)

Goldie: 2012-01-12 07:10:50

Give some more TCs please..

no problem got it..

Last edit: 2012-01-12 07:20:33

Added by:Mahesh Chandra Sharma
Date:2011-01-28
Time limit:2.519s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64