paste bin

#include <cstdio>
#include <algorithm>
#define MAXN 5007
using std::min;


int main(void)
{
     int i,j,N;
     int dp[MAXN];
     scanf("%d",&N);
     dp[1]=1;
     for(i=2;i<=N;i++)
     {
         dp[i]=dp[i-1]+1;
         for(j=2;j*j<=i;j++)
         {
             if(i%j==0)
             {
                 dp[i]=min(dp[i],dp[i/j]+dp[j]);
             }
         }
     }

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

     return 0;
}