Problem hidden

NTHPRIME - Nth Prime

There is no tedious description for this problem. You are just required to calculate and output the Nth prime number.

Input

The input consists of a single line containing an integer N, N ≤ 109.

Output

For each input file, output the Nth prime number.

Example

Input:
4

Output:
7

Note

The source limit is enabled to 4000B in order to restrict and discourage sending solutions with pre-computed tables.

 


Adicionado por:sgtlaugh
Data:2015-08-25
Tempo limite:2.667s
Tamanho do fonte:4000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP GOSU PERL6 PY_NBC SCALA TCL
Origem:Own Problem
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.