The problem statement is really simple (the constraints maybe not). There are some queries. You are to give the answers.

Input

An integer stating the number of queries Q(equal to 100000), and Q lines follow, each containing one integer K between 1 and 50000000 inclusive.

Output

Q lines with the answer of each query: the Kth prime number.

Example

Input:
8
1
10
100
1000
10000
100000
1000000
10000000

Output:
2
29
541
7919
104729
1299709
15485863
179424673