#include <stdio.h>

//dp 밑에서부터 다 채움 (반복문) 점화식 F(n)=min(F(n/3)+1,F(n/2)+1,F(n-1)+1)
int bottom_up(int n) {
    int dp[1000001];
    // 초기값(기저)
    dp[1]=0;

    for(int i=2; i<=n; i++) {
        dp[i]=dp[i-1]+1;
        
        if(i%2==0) {
            int tmp=dp[i/2]+1;
            if(dp[i]>tmp) dp[i]=tmp;
        } 
        if(i%3==0) {
            int tmp=dp[i/3]+1;
            if(dp[i]>tmp) dp[i]=tmp;
        } 
    }  
    return dp[n];
}

int main() {
    int n;
    scanf("%d",&n);
    printf("%d",bottom_up(n));
    return 0;
}