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 ≤ 10^9.

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.