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}$ .