N-th Prime Number Finder

In this problem, you are required to find the N-th prime number for multiple test cases. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. You will be given an integer T representing the number of test cases, followed by T positive integers. For each integer N, output the N-th prime number.

The challenge is to compute the answer efficiently using an algorithm such as the Sieve of Eratosthenes, with an appropriate upper bound estimate based on n. Recall that by the Prime Number Theorem, the N-th prime can be approximated by \( n (\ln n + \ln\ln n) \) for sufficiently large \( n \).

inputFormat

The input starts with a single integer T representing the number of test cases. The next line contains T space-separated positive integers. Each integer denotes the position \( N \) (1-indexed) of the prime number that needs to be found.

Example:

3
1 5 10

outputFormat

For each test case, output the corresponding N-th prime number on a new line.

Example Output:

2
11
29

## sample

3
1 5 10

2
11
29

</p>