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

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.

"); $(this).append($copy); var clipboard = new Clipboard('#' + cpyId, { text: function(trigger) { return document.querySelector('#' + preId).innerText; } }); var isInput = $(this).parent().hasClass("input"); clipboard.on('success', function(e) { if (isInput) { Codeforces.showMessage("The example input has been copied into the clipboard"); } else { Codeforces.showMessage("The example output has been copied into the clipboard"); } e.clearSelection(); }); }); autosize($('.test-explanation textarea')); });