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.

Input

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

Output a single integer — the minimum possible $*X*_{0}$.

Note

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