CF923A.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.

爱丽丝和鲍勃每天以一场快速游戏开始。他们首先选择一个起始数 $X_0 \geq 3$，并尝试通过以下过程达到一百万。

爱丽丝先手，之后两人轮流进行。在第 $i$ 轮中，轮到的玩家需选择一个小于当前数的一个质数，并宣布该质数的、不小于当前数的最小倍数。

形式化地，他或她选择一个质数 $p < X_{i-1}$，然后找出满足 $p \mid X_i$ 的最小 $X_i \geq X_{i-1}$。注意：若所选质数 $p$ 已整除 $X_{i-1}$，则数值保持不变。

夏娃目睹了游戏进行两轮后的状态。给定 $X_2$，请帮她确定最小可能的起始数 $X_0$。注意：玩家不一定采取最优策略。你应考虑所有可能的游戏演化路径。

The input contains a single integer _X_2 (4 ≤ _X_2 ≤ 106). It is guaranteed that the integer _X_2 is composite, that is, is not prime.

输入包含一个整数 $X_2$（$4 \leq X_2 \leq 10^6$）。保证该整数 $X_2$ 是合数，即不是质数。

Output a single integer — the minimum possible _X_0.

输出一个整数——最小可能的 $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.

在第一组测试中，最小的可能起始数为 $X_0 = 6$。游戏的一种可能进行过程如下：

• 爱丽丝选择质数 $5$，并宣布 $X_1 = 10$；
• 鲍勃选择质数 $7$，并宣布 $X_2 = 14$。

在第二组测试中，令 $X_0 = 15$：

• 爱丽丝选择质数 $2$，并宣布 $X_1 = 16$；
• 鲍勃选择质数 $5$，并宣布 $X_2 = 20$。