A11468. Primal Sport

Alice and Bob begin their day with a quick game. They first choose a starting number $X_{0}>=3$ and try to reach one million by the process described below.

Alice goes first and then they take alternating turns. In the $i$ -th turn, the player whose turn it is selects a prime number smaller than the current number, and announces the smallest multiple of this prime number that is not smaller than the current number.

Formally, he or she selects a prime $p<X_{i-1}$ and then finds the minimum $X_{i}>=X_{i-1}$ such that $p$ divides $X_{i}$ . Note that if the selected prime $p$ already divides $X_{i-1}$ , then the number does not change.

Eve has witnessed the state of the game after two turns. Given $X_{2}$ , help her determine what is the smallest possible starting number $X_{0}$ . Note that the players don't necessarily play optimally. You should consider all possible game evolutions.

The input contains a single integer $X_{2}$ ( $4<=X_{2}<=10^{6}$ ). It is guaranteed that the integer $X_{2}$ is composite, that is, is not prime.

Output a single integer — the minimum possible $X_{0}$ .

In the first test, the smallest possible starting number is $X_{0}=6$ . One possible course of the game is as follows:

- Alice picks prime 5 and announces $X_{1}=10$
- Bob picks prime 7 and announces $X_{2}=14$ .

In the second case, let $X_{0}=15$ .

- Alice picks prime 2 and announces $X_{1}=16$
- Bob picks prime 5 and announces $X_{2}=20$ .