KPRIMES2 - Finding the Kth Prime (Hard)

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

Added by:Alfonso² Peterssen
Date:2010-04-09
Time limit:1.399s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC
Resource:Thanks to TDuke

hide comments
2013-12-26 15:00:09 pika_pika
http://primes.utm.edu/nthprime/index.php#nth
for queries of nth prime pi(n) and random primes
2012-12-18 06:55:39 triveni
Anyone please reply what is the output for
50000000???

Last edit: 2012-12-18 06:56:43
2011-01-28 18:39:12 kuszi
@James Waldby Corrected
2011-01-28 18:38:50 Abel Nieto Rodriguez
@James Waldby
It's clearly a typo.
2011-01-28 18:38:50 James Waldby
The example shows 8 lines of input after the number Q = 9 and similarly 8 lines of output. Is that an error in the example? (Or does it show some condition the program needs to treat?)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.