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 N-th preprime in a single line.

Example

Input:
4
2
4
24
43765

Output:
8
14
77
193539