Primal Sport

越学越掂是个贪玩的孩子。 这天，越学越掂和他的**一个**朋友正在玩游戏，轮流来的，首先给出一个$X0$,选取一个$P1$（$P1$比当前数值小），然后让找$P1$的某一倍数使得它刚好大于等于当前数值(等于的时候是说这个质数本身就是当前数值的因数)，这个数字便是下一个数字。再如是进行一轮。题目给出$X2$(这个数字是个非质数)，希望你能求出满足要求的最小的$X0$。

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

14

6

20

15

8192

8191

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