#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

int n,dp[1024];
vector<int> v[1024];

int main()
{
    int i,j;
    scanf("%d",&n);
    dp[2]=1;
    for(i=2;i<n;i++)
    {
        v[i].push_back(i);
        for(j=2;j<=i/2;j++)
         if((i/j)*j==i)v[i].push_back(i/j);
        v[i].push_back(1);
        if(i>2)dp[i]=1000000000;
    }
    if(n!=2)dp[n]=1000000000;
    for(i=2;i<n;i++)
    {
        for(j=0;j<v[i].size();j++)
         if(i+v[i][j]<=n)
          dp[i+v[i][j]]=min(dp[i+v[i][j]],dp[i]+1);
    }
    printf("%d\n",dp[n]);
}
