Alice and Bob begin their day with a quick game. They first choose a starting number X₀ ≥ 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₂, help her determine what is the smallest possible starting number X₀. Note that the players don't necessarily play optimally. You should consider all possible game evolutions.

The input contains a single integer X₂ (4 ≤ X₂ ≤ 10⁶). It is guaranteed that the integer X₂ is composite, that is, is not prime.

Output a single integer — the minimum possible X₀.