/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();

		int dp[]=new int[n+1];
		for(int i=2;i<=n;i++){
			int s1=dp[i-1]+1;
			int s2=Integer.MAX_VALUE;
			int s3=Integer.MAX_VALUE;
			int x=Integer.MAX_VALUE;
			if(i%2==0){
				s2=dp[i/2]+1;
			}
			if(i%3==0){
				s3=dp[i/3]+1;
			}
			if(i%2!=0 && i%3!=0){
				x=Math.max(dp[i-1],dp[i-2])+1;
			}
			dp[i]=Math.min(s1,Math.min(s2,Math.min(s3,x)));
		}
		System.out.println(dp[n]);
	}
}