XerK had prepared his new problem with some sums of primes up to some bounds. His results are well here, but he forgot the bounds.

Your task is to find which was the last prime in the sum.

This problem is extremely simple, but you have to be extremely fast.

Input

The lonely line of input contains an integer S.

Output

You have to print the last prime P such that sum(prime from 2 to P) = S.

Examples

Input 1:
77

Output 1:
19

Input 2:
24739512092254535

Output 2:
999999937

Explanation

The first sum was 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 = 77

Constraints

0 < P <= 10^12

The challenge problem SUMPRIM1 is the reverse task.
Time limit is set to allow some slow languages to finish in time, it could be hard.
For your information, there's a total of 20 input files.
;-) Have fun.

You may try before an excellent tutorial problem (Twin Primes) and make some speed experiments.
You could take benefit too by working with PRINT, another excellent tutorial problem.