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.
The first line contains the number of test cases t(t≤104).
Each test contains one positive integer n(n≤5⋅105).
For each test case print the n-th prime number on a separate line.