n-th prime

Consider a list of prime numbers: $2,3,5,7,11,13,...$. For example, the $6$-th prime number is $13$.

Find the $n$-th prime number.

Input

The first line contains the number of test cases $t(t\le 10^4)$.

Each test contains one positive integer $n(n\le 5\cdot 10^5)$.

Output

For each test case print the $n$-th prime number on a separate line.

Examples