#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

int n;
int sol;
int memo[1001];

int f(int x)
{
    int &ret = memo[x];
    
    if(~ret)
        return ret;
    
    ret = 1 + f(x - 1);
    int r = (int)sqrt(x);
    for(int i = 2; i <= r; ++i)
        if(x % i == 0)
            ret = min(ret, f(i) + f(x / i));
    
    return ret;
}

int main()
{
    memset(memo, -1, sizeof memo);
    memo[1] = 0;
    memo[2] = 1;
    
    scanf("%d", &n);
    printf("%d\n", f(n));
    //system("pause");
    return 0;
}
