#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

#define MAX 1010

using namespace std;

int dp[MAX];
int n;

int main(void) {
  scanf("%d", &n);
  
  for ( int i = 2; i <= n; ++i ) {
    dp[i] = dp[i-1] + 1;
    for ( int j = 2; j < i; ++j ) {
      if ( i % j != 0 ) continue;
      dp[i] = min( dp[i], 1 + dp[ i / j * (j - 1) ] );
    }
  }
  
  printf("%d\n", dp[n]);
  return 0;
}
