#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)5e5 + 228;
const char nxtl = '\n';
const int mod = (int)1e9 + 7;
const double eps = (double)1e-7;
template <typename T>
inline bool updmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool updmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
int get(int n) {
  vector<int> cur;
  int nn = n;
  for (int i = 2; i * 1ll * i <= n; ++i) {
    while (n % i == 0) {
      if (i > 1) cur.push_back(i);
      n /= i;
    }
  }
  if (n > 1) cur.push_back(n);
  sort(cur.begin(), cur.end());
  cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
  n = nn;
  int res = n;
  for (auto &to : cur)
    if (n - to + 1 >= 3) updmin(res, max(1, n - to + 1));
  return res;
}
int n;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  int nn = n;
  vector<int> cur;
  for (int i = 2; i * 1ll * i <= n; ++i) {
    while (n % i == 0) {
      if (i > 1) cur.push_back(i);
      n /= i;
    }
  }
  if (n > 1) cur.push_back(n);
  sort(cur.begin(), cur.end());
  cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
  for (auto &to : cur) cerr << to << nxtl;
  int res = INT_MAX;
  n = nn;
  for (auto &to : cur) {
    for (int i = 1; i < n; ++i) {
      if (i / to == n / to - 1 && i % to != 0 && updmin(res, get(i)))
        ;
    }
  }
  cout << res << nxtl;
  return 0;
}
