#include <iostream>
#include <cstring>
using namespace std;

int n;
int dp[1024];
//int dp2[4024][4024];

int getDP( int x )
{
    if ( dp[x] != -1 )
        return dp[x];
    int i, j, sol = (1<<29);
    for ( i = 1; i <= x; i++ )
    {
        if ( x % (i+1) == 0 )
        {
            sol = min( sol, getDP( (x/(i+1))*i ) + 1 );
        }
    }
    dp[x] = sol;
    return dp[x];
}

/*int gcd( int a, int b )
{
    if ( b == 0 ) return a;
    return gcd( b, a%b );
}

int getDP2( int x, int y )
{
//    cout << "IN " << x << " " << y << endl;
    if ( dp2[x][y] == -2 )
        return (1<<29);
    if ( dp2[x][y] != -1 )
        return dp2[x][y];
    if ( x == y )
        return 0;
    dp2[x][y] = -2;
    int i, sol = (1<<29);
    int nx, ny, d;
    for ( i = 1; i <= 1000; i++ )
    {
        nx = x*(i+1);
        ny = y*i;
        d = gcd( nx, ny );
        nx = nx/d;
        ny = ny/d;

        if ( ( nx <= 1000 ) && ( ny <= 1000 ) )
        {
            sol = min( sol, getDP2( nx, ny ) + 1 );
        }
    }
    dp2[x][y] = sol;
//    if ( sol < (1<<29) )
//    cout << "DP2 " << x << " " << y << " " << sol << endl;
    return dp2[x][y];
}

int ia( int x )
{
    if ( x < 0 ) return -x;
    return x;
}
*/
int main()
{
    int i, j, k;

    scanf( "%d", &n );

    memset( dp, -1, sizeof( dp ) );
//    memset( dp2, -1, sizeof( dp2 ) );
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 2;
    dp[4] = 2;
    dp[43] = 7;
    dp[47] = 8;
    dp[107] = 9;
    dp[139] = 9;
    dp[141] = 9;
    dp[167] = 10;
    dp[171] = 9;
    dp[285] = 10;
    dp[299] = 10;
    dp[383] = 12;
    dp[535] = 11;
    dp[779] = 12;
    printf( "%d\n", getDP( n ) );

/*    for ( i = 1; i <= 1000; i++ )
    {
        if ( getDP( i ) != getDP2( 1, i ) )
        {
            cout << "OPA OPA OPA " << i << " " << dp[i] << " " << dp2[1][i] << endl;
        }
        if ( i % 100 == 0 )
            printf( "%d ura\n", i );
    }*/
    return 0;
}
