/* 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]);
	}
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCQlTY2FubmVyIHNjPW5ldyBTY2FubmVyKFN5c3RlbS5pbik7CgkJaW50IG49c2MubmV4dEludCgpOwoKCQlpbnQgZHBbXT1uZXcgaW50W24rMV07CgkJZm9yKGludCBpPTI7aTw9bjtpKyspewoJCQlpbnQgczE9ZHBbaS0xXSsxOwoJCQlpbnQgczI9SW50ZWdlci5NQVhfVkFMVUU7CgkJCWludCBzMz1JbnRlZ2VyLk1BWF9WQUxVRTsKCQkJaW50IHg9SW50ZWdlci5NQVhfVkFMVUU7CgkJCWlmKGklMj09MCl7CgkJCQlzMj1kcFtpLzJdKzE7CgkJCX0KCQkJaWYoaSUzPT0wKXsKCQkJCXMzPWRwW2kvM10rMTsKCQkJfQoJCQlpZihpJTIhPTAgJiYgaSUzIT0wKXsKCQkJCXg9TWF0aC5tYXgoZHBbaS0xXSxkcFtpLTJdKSsxOwoJCQl9CgkJCWRwW2ldPU1hdGgubWluKHMxLE1hdGgubWluKHMyLE1hdGgubWluKHMzLHgpKSk7CgkJfQoJCVN5c3RlbS5vdXQucHJpbnRsbihkcFtuXSk7Cgl9Cn0=

MTAw

100