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