#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> p;
vector<bool> prime(20009);
int memo[2500][20009];
int INF=200000000;
int a=0;

int main(){
  cin >> N;
  for(int i=2;i<=N;i++)prime[i]=1;
  for(int i=2;i<=N;i++){
    if(prime[i]){
      p.push_back(i);
      for(int j=2*i;j<=N;j+=i){prime[j]=0;}
    }
  }
  int s=p.size();
  for(int i=0;i<=s;i++){
    for(int j=0;j<=N;j++){memo[i][j]=INF;}
  }
  memo[0][0]=0;
  for(int i=0;i<s;i++){
    for(int j=0;j<=N;j++){
      if(j<p[i]){memo[i+1][j]=memo[i][j];}
      else{
        if(memo[i][j]==INF && memo[i][j-p[i]]==INF){a++;}
        else if(memo[i][j]!=INF){memo[i+1][j]=memo[i][j];}
        else if(memo[i][j]==INF){memo[i+1][j]=memo[i][j-p[i]]+1;}
        else{memo[i+1][j]=max(memo[i][j],memo[i][j-p[i]]+1);}
      }
    }
  }
  if(memo[s][N]==INF){cout << -1 << endl;}
  else{cout << memo[s][N] << endl;}
}