#include <cstdio>
#include <algorithm>

using namespace std;

int dp[1005];

int gcd( int a, int b ) { return !b ? a : gcd( b, a%b ); }

int main( void ) {
    int n;
    scanf( "%d", &n );
    dp[2] = 1;
    for( int i = 3; i <= n; ++i ) {
        dp[i] = i-1;
        for( int j = 2; j < i; ++j ) {
            int g = gcd( i, j );
            if( (i/g)-1 == (j/g) ) dp[i] = min( dp[i], dp[j]+1 );
        }
    }
    printf( "%d\n", dp[n] );
    return 0;
}