Problem J
Consecutive Prime Sums

You are given a positive integer $n$ and should print the prime number $< n$ that can be written as the sum of the greatest number of consecutive primes.

For example $41$ can be written as $2 + 3 + 5 + 7 + 11 + 13$ and it can be seen that $41$ is the prime $< n$ that can be written as the sum of the most consecutive primes. Note that the sum does not have to begin with the prime $2$.

Input

The first and only line of input contains a positive integer $100 \leq n \leq 5 \cdot 10^{6}$.

Output

Print the prime $< n$ that can be written as the sum of the most consecutive primes. If there are ties print the smallest number.

100000

92951