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

int n;
int dp[1024];

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 ia( int x )
{
    if ( x < 0 ) return -x;
    return x;
}

int main()
{
    int i, j, k;

    scanf( "%d", &n );

    memset( dp, -1, sizeof( dp ) );
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 2;
    dp[4] = 2;
    printf( "%d\n", getDP( n ) );
    return 0;
}
