[백준] P1463

import java.util.Arrays;
import java.util.Scanner;

public class P1463 {
	
	/*
	 * ex) 10
	 * 
	 * 0 0 0 0 0 0 0 0 0 0 0 =>
	 *  
	 * Arrays.fill(dp,10)	-> 10 10 10 10 10 10 10 10 10 10 10
	 * dp[1]=0				-> 10 0 10 10 10 10 10 10 10 10 10
	 * 
	 * for문 수행				
	 * i=1					-> 10 0 1 1 10 10 10 10 10 10 10
	 * i=2					-> 10 0 1 1 2 10 2 10 10 10 10
	 * i=3					-> 10 0 1 1 2 10 2 10 10 2 10
	 * i=4					-> 10 0 1 1 2 3 2 10 3 2 10
	 * i=5					-> 10 0 1 1 2 3 2 10 3 2 4
	 * i=6					-> 10 0 1 1 2 3 2 3 3 2 4
	 * i=7					-> 10 0 1 1 2 3 2 3 3 2 4
	 * i=8					-> 10 0 1 1 2 3 2 3 3 2 4
	 * i=9					-> 10 0 1 1 2 3 2 3 3 2 3
	 * 
	 * return dp[10]		-> 3
	 */
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), dp[] = new int[n + 1];
		Arrays.fill(dp, n); // dp 배열을 n으로 채움
		dp[1] = 0;

		for (int i = 1; i < n; i++) { // 1로 시작하여 +1, *2, *3 을 수행하며 +1, *2, *3 번째 인덱스에 최소값을 넣음
			if (i + 1 <= n) {
				dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1);
			}
			if (i * 2 <= n) {
				dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);
			}
			if (i * 3 <= n) {
				dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);
			}
		}

		System.out.println(dp[n]);
		sc.close();
	}
}