#include <cstdio>
#include <algorithm>
using namespace std;

int a[1 << 20];
int dp[1 << 20];

int go ( int pos , int k , int mul1 , int mul2 ) {
	if ( pos == k + 1 )
		return mul1 == mul2;
	int i;
	
	for (i = 1; i <= 20; i++) {
		a[pos] = i;
		
		if ( go ( pos + 1 , k , mul1 * (a[pos] + 1) , mul2 * a[pos] ) )
			return 1;
	}
	
	return 0;
}

int main() {
	int i , j , k;
	int n = 2000;
	
	dp[1] = 0;
	dp[2] = 1;
	for (i = 3; i <= n; i++) {
		dp[i] = 1 << 30;
		
		for (j = 1; j < i; j++)
			if ( i % (j + 1) == 0 ) {
// 				printf ( "%d    %d %d   %d %d\n" , i , i / (j + 1) , j , dp[i / (j + 1)] , dp[j] );
				dp[i] = min ( dp[i] , dp[i / (j + 1)] + dp[j] + 1 );
			}
			
// 		printf ( "%d %d\n" , i , dp[i] );
	}
	
	scanf ( "%d" , &n );	printf ( "%d\n" , dp[n] );	return 0;
	
	for (i = 2; i <= 45; i++) {
		for (k = 1; k <= 8; k++) {
			if ( go ( 1 , k , 1 , i ) ) {
				printf ( "n = %d   k = %d  fast = %d\n" , i , k , dp[i] );
				if ( k != dp[i] )
					printf ( "FUCK\n" );
				for (j = 1; j <= k; j++)
					printf ( "%d " , a[j] );
				printf ( "\n\n" );
				fflush ( stdout );
				break;
			}
		}
		
		if ( k == 9 )
			printf ( "FUCK\n" );
	}
	
	return 0;
}
