DWITE Online Computer Programming Contest, January 2011, Problem 2

Math sure likes their prime numbers, those with only two factors, ~1~ and itself. ~2,3,5,7~ are the first four prime numbers, written in a sequence (numbers following each other). We've made up a new sequence of numbers, primal numbers that are based on the values of the prime numbers sequence.

The ~1~st primal number is the value that is in the position #(value of the ~1~st prime) in the prime sequence. That is, the ~1~st prime is ~2~, and the prime number in ~2~nd position is ~3~, so the ~1~st primal number is ~3~.

The ~2~nd primal number is in position #(value of ~2~nd prime) in the prime sequence. ~2~nd prime is ~3~, and the ~3~rd prime is ~5~; so the ~2~nd primal number is ~5~. The sequence continues in the same pattern; ~3, 5, 11, 17~ are the first four primal numbers.

The input will contain 5 lines, integers ~1 \le N \le 1000~.

The output will contain 5 lines, each the ~N~th primal number.

Note: think about performance for large values of ~N~. The ~1000~th prime number is ~7919~, so you'd need the ~7919~th prime number to figure out what the ~1000~th primal number is.

Sample Input

4
24
8
1
15

Sample Output

17
461
67
3
211

Problem Resource: DWITE