#include<iostream>
using  namespace std;
int n;
int prime [1002];
int dp[1003];
void read ()
{
     cin>>n;
}
void resheto ()
{
     int r;
     for(int i=1;i<=100;i++)
     {
           r=(i*i);
           while(r<=1000)
           {
                         prime[r]=1;
                         r+=i;
           }  
     }
}
int ask (int x)
{
    int min=dp[x-1]+1;
    if(prime[x]==0)return min;
    int i,r,p;
    if(x%2==0) return dp[x/2]+1;
    for(i=3;(i*i)<=x;i++)
    {
             if(x%i==0)
             {
                       r=x/i;
                       if((dp[r]+dp[i])<min)min=(dp[r]+dp[i]);
             }            
    }
    return min;
}
void solve ()
{
     resheto();
     dp[2]=2;
     dp[3]=2;
     dp[4]=2;
     dp[5]=3;
     for(int i=6;i<=n;i++)
     {
             int tek=ask(i);
             dp[i]=tek;
     }
    
     cout<<dp[n]<<endl;
}
int main ()
{
    read ();
    solve ();
}
