/* 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 int makezeroDP(int n){
       int[] table = new int[n+1];
       table[1] = 1; table[2] = 2; table[3] = 3;
       int res;
       for (int i = 4; i <= n; i++) {
          res = 1 + table[i-1];
          int a = 2;
          while (a * a <= i) {
             if (i % a == 0)
                res = Math.min(res, 1 + table[i / a]);
             a += 1;
          }
          table[i] = res;
       }
       return table[n];
	}
 
	public static void main (String[] args) throws java.lang.Exception
	{ 
		int n = 145;//999999;
     	System.out.println(makezeroDP(n));
	}
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgaW50IG1ha2V6ZXJvRFAoaW50IG4pewogICAgICAgaW50W10gdGFibGUgPSBuZXcgaW50W24rMV07CiAgICAgICB0YWJsZVsxXSA9IDE7IHRhYmxlWzJdID0gMjsgdGFibGVbM10gPSAzOwogICAgICAgaW50IHJlczsKICAgICAgIGZvciAoaW50IGkgPSA0OyBpIDw9IG47IGkrKykgewogICAgICAgICAgcmVzID0gMSArIHRhYmxlW2ktMV07CiAgICAgICAgICBpbnQgYSA9IDI7CiAgICAgICAgICB3aGlsZSAoYSAqIGEgPD0gaSkgewogICAgICAgICAgICAgaWYgKGkgJSBhID09IDApCiAgICAgICAgICAgICAgICByZXMgPSBNYXRoLm1pbihyZXMsIDEgKyB0YWJsZVtpIC8gYV0pOwogICAgICAgICAgICAgYSArPSAxOwogICAgICAgICAgfQogICAgICAgICAgdGFibGVbaV0gPSByZXM7CiAgICAgICB9CiAgICAgICByZXR1cm4gdGFibGVbbl07Cgl9CiAgICAgCglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiAoU3RyaW5nW10gYXJncykgdGhyb3dzIGphdmEubGFuZy5FeGNlcHRpb24KCXsgCgkJaW50IG4gPSAxNDU7Ly85OTk5OTk7CiAgICAgCVN5c3RlbS5vdXQucHJpbnRsbihtYWtlemVyb0RQKG4pKTsKCX0KfQ==