#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;

#define inf 1999888777
#define eps 0.000001
#define pi 3.14159265358979


int main() {

     int n,i,j,res[1111];
     scanf("%d", &n);

     res[1]=1; res[2]=1;
     for(i=3; i<=n; i++) {
     	res[i]=i-1;
     	for(j=2; j<i; j++) {
     		if (i%j == 0) {
     			if (res[j]+res[i/j] < res[i]) res[i]=res[j]+res[i/j];
     		}
     		if ( (i*j)%(j+1) == 0 ) {
     		    if (res[(i*j)/(j+1)] + 1 < res[i]) res[i]=res[(i*j)/(j+1)] + 1;
     		}
     	}
     }

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

     return 0;
}