Primal Sport

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

Examples

input

14

output

6

input

20

output

15

input

8192

output

8191

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.

Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int x;
cin >> x;
vector<int> p(x + 1);
for (int i = 1; i <= x; i++) {
    p[i] = i;
  }
  for (int i = 2; i <= x; i++) {
    if (p[i] == i) {
      for (int j = i + i; j <= x; j += i) {
        p[j] = min(p[j], i);
      }
    }
  }
  const int inf = (int) 1e9;
  vector<int> best(x + 1, inf);
for (int i = 1; i <= x; i++) {
    int tmp = i;
    while (tmp > 1) {
int d = p[tmp];
if (i != d) {
best[i] = min(best[i], i - d + 1);
}
tmp /= p[tmp];
}
}
int res = inf;
{
int tmp = x;
while (tmp > 1) {
int d = p[tmp];
for (int j = x - d + 1; j <= x; j++) {
        res = min(res, best[j]);
      }
      tmp /= p[tmp];
    }
  }
  cout << res << '\n';
  return 0;
}