#include <bits/stdc++.h>

 using namespace std;

 const int N=1e6+;

 int prime[N];

 int dp[N];

 int main ()

 {

     memset (dp,0x3f,sizeof(dp));

     for (int i=;i<N;i++) {

         if (!prime[i])  { prime[++prime[]]=i; dp[i]=; }

         for (int j=;j<=prime[]&&i*prime[j]<N;j++) {

             prime[i*prime[j]]=;

             if (i%prime[j]==) break;

         }

     }

     dp[]=;

     for (int i=;i<N;i++) {

         dp[i]=min (dp[i],dp[i-]+);

         for (int j=;j<=prime[]&&i*prime[j]<N;j++)

             dp[i*prime[j]]=min ( dp[i*prime[j]],dp[i]+); //核♥： 用已知的这个数与素数相乘去更新比它大的数

     }     while (~scanf ("%d",&n))

         printf ("%d\n",dp[n]);

     return ;

 }