#include <iostream>
#include <cstring>

using namespace std;


int dp[1026];

int go ( int N ){
    if ( dp[N] == ( 1 << 30 ) ) cout << "ei sq si eba maikata\n";
    if ( dp[N] != -1 ) return dp[N];

    dp[N] = ( 1 << 30 );

    for ( int i = 2; i <= N; ++i ){
        if ( ( N / i ) * i == N ){
            go ( N / i * ( i - 1 ) );
            if ( dp[ N / i * ( i - 1 ) ] + 1 < dp[N] )
                dp[N] = dp[ N / i * ( i - 1 ) ] + 1;
        }
    }

    return dp[N];
}
int main(){
    int N;

    cin >> N;

    memset ( dp, -1, sizeof ( dp ) );
    for ( int i = 0; i <= 10; ++i )
        dp[ ( 1 << i ) ] = i;

    cout << go ( N ) << endl;
}
