The problem statement is simple, you have to write the nth prime number to the output.

Input

The first line contains the number of test cases,t.
Then t lines follow containing an integer n.

1<=t<=1000
1<=n<=664579

Output

The output contains t lines, each contains an integer, the answer for that particular value of n.

Example

Input:
2
3
10

Output:
5
29