Primal Sport

1000ms

262144K

Description:

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.

Input:

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:

Output a single integer — the minimum possible X₀.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Note:

In the first test, the smallest possible starting number is X₀ = 6. One possible course of the game is as follows:

Alice picks prime 5 and announces X₁ = 10
Bob picks prime 7 and announces X₂ = 14.

In the second case, let X₀ = 15.

Alice picks prime 2 and announces X₁ = 16
Bob picks prime 5 and announces X₂ = 20.

Informação

Provedor Codeforces

Código CF923A