#include <bits/stdc++.h>
using namespace std;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const long long NLINF = 0xf7f7f7f7f7f7f7f7;
const int INF = 0x3f3f3f3f, NINF = 0xf7f7f7f7;
const int MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
const int N = 1e6;
int x, pf[N + 5], dp[N + 5][5];
int solve(int v, int k) {
  if (dp[v][k] != -1) return dp[v][k];
  if (pf[v] == v or !k) return v;
  int v_orig = v, ret = INF;
  while (v > 1) {
    int x = (v_orig / pf[v] - 1);
    for (int i = pf[v] * x; i < min(pf[v] * x + 100, pf[v] * (x + 1)); i++)
      ret = min(ret, solve(i + 1, k - 1));
    int curd = pf[v];
    while (v % curd == 0) v /= curd;
  }
  return dp[v][k] = ret;
}
int main() {
  scanf("%d", &x);
  for (int i = 2; i <= N; i++) {
    if (pf[i]) continue;
    for (int j = i; j <= N; j += i) pf[j] = i;
  }
  memset(dp, -1, sizeof dp);
  printf("%d\n", solve(x, 2));
}
