#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <math.h>
using namespace std;

#define ll long long
#define INF 987654

#define MaxN 1001

int n;
int dp[MaxN];

int main()
{

	scanf("%d",&n);

  memset(dp, 0, sizeof(dp));
  dp[2] = 1;
  for (int i = 3; i <= n; ++i) {
       dp[i] = i-1;
       for (int j = 2; j < i; ++j) {
         if ( (i-1) % j == 0 ) {
             dp[i] = min(dp[i],dp[j]+dp[(i-1)/j]+1);
         }
         if ( i % j == 0 ) {
             dp[i] = min(dp[i],dp[j]+dp[i/j]);
         }
       }
  }
  printf("%d\n",dp[n]);

	return 0;
}