#include <bits/stdc++.h>
using namespace std;
bool bz[1000001];
int c[1000001];
int main() {
  int n;
  scanf("%d", &n);
  memset(bz, true, sizeof(bz));
  bz[1] = false;
  for (int i = 2; i <= n; i++) {
    for (int j = 2; j <= n / i; j++) {
      bz[i * j] = false;
    }
  }
  int m = n;
  int total = 0;
  for (int i = 2; i <= n - 1; i++) {
    if (bz[i] == false) continue;
    if (m % i == 0) {
      total++;
      c[total] = i;
    }
    while (m % i == 0) {
      m = m / i;
    }
  }
  int min1 = n + 1;
  for (int i = 1; i <= total; i++) {
    if (c[i] == 17) {
      m++;
      m--;
    }
    for (int j = 1; j <= n - 1; j++) {
      if (c[i] == 17) {
        m++;
        m--;
      }
      if (bz[j] == true) {
        int q = ((n - c[i]) / j) * j;
        while (q <= n - c[i]) q = q + j;
        if (q == 10) {
          n++;
          n--;
        }
        if ((q == j) || (q > n)) continue;
        if (min1 > q - j + 1) min1 = q - j + 1;
        if (min1 == 20) {
          n++;
          n--;
        }
      }
    }
  }
  printf("%d", min1);
}
