EPR - PrePrimes

no tags 

A number is preprime if it has exactly 4 positive integer divisors. For example, 6 is preprime because its divisors are 1, 2, 3, and 6. The integers 6, 8, 10, 14 form the beginning of an infinite sequence of preprime numbers. Find the n-th element of this sequence, where n is a 1-based index.

Input

First line contains an integer T <= 20 - the number of test cases. Following each line contains a single integer 1<= N <= 1000000.

Output

For each test case, print Nth preprime in a single line.

 

Example

Input:

4
2
4
24
43765

Output:

8
14
77
193539

hide comments
nadstratosfer: 2018-05-25 11:58:16

Classical-grade problem, if at the easier end of the NT category. Good constraints, several approaches possible, fun to optimize. Damn shame it's been rotting in tutorial for 7 years with less than a dozen solvers.. Admins, if possible please add #number-theory tag.

John and the cows: 2013-08-17 15:47:37

yes, finally AC :)


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