#include <bits/stdc++.h>
using namespace std;
int ps, p[200005], chk[200005];
bool vis[200005];
void ppm() {
  for (int i = 2; i < 200005; i++) {
    if (!vis[i]) p[++ps] = i, chk[i] = 1;
    for (int j = 1; j <= ps && i * p[j] < 200005; j++) {
      int k = i * p[j];
      vis[k] = 1;
      if (!vis[i]) chk[k] = 1;
      if (i % p[j] == 0) break;
    }
  }
}
vector<int> vec;
int num[200005];
bool ris[200005];
int main() {
  ppm();
  for (int i = 1; i < 200005; i++)
    if (chk[i]) vec.push_back(i);
  num[0] = 0;
  for (int i = 1; i < 120005; i++) {
    for (int j = 0; j < vec.size(); j++) {
      if (vec[j] > i) break;
      ris[num[i - vec[j]]] = 1;
    }
    for (int j = 0; j < 200005; j++)
      if (!ris[j]) {
        num[i] = j;
        break;
      };
    for (int j = 0; j < vec.size(); j++) {
      if (vec[j] > i) break;
      ris[num[i - vec[j]]] = 0;
    }
  }
  printf("%d\n", num[120000]);
  return 0;
}
