import java.util.*;
import java.lang.*;
import java.io.*;
import java.lang.Math;
 
class Main
{
	public static int max = 5001;
	static int [] x = new int[max];
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k;
		x[1] = 1;
		x[2] = 2;
		for (int i = 3; i <= n; i++) {
			x[i] = x[i-1]+1;
			for (int j = 2; j <= Math.sqrt(n); j++) {
				if(i % j == 0) {
					k = x[j] + x[i/j];
					if( k < x[i]) x[i] = x[j] + x[i/j];
				}
			}
		}
		System.out.println(x[n]);
	}
}

aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CmltcG9ydCBqYXZhLmxhbmcuTWF0aDsKCmNsYXNzIE1haW4KewoJcHVibGljIHN0YXRpYyBpbnQgbWF4ID0gNTAwMTsKCXN0YXRpYyBpbnQgW10geCA9IG5ldyBpbnRbbWF4XTsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCVNjYW5uZXIgaW4gPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pOwoJCWludCBuID0gaW4ubmV4dEludCgpOwoJCWludCBrOwoJCXhbMV0gPSAxOwoJCXhbMl0gPSAyOwoJCWZvciAoaW50IGkgPSAzOyBpIDw9IG47IGkrKykgewoJCQl4W2ldID0geFtpLTFdKzE7CgkJCWZvciAoaW50IGogPSAyOyBqIDw9IE1hdGguc3FydChuKTsgaisrKSB7CgkJCQlpZihpICUgaiA9PSAwKSB7CgkJCQkJayA9IHhbal0gKyB4W2kval07CgkJCQkJaWYoIGsgPCB4W2ldKSB4W2ldID0geFtqXSArIHhbaS9qXTsKCQkJCX0KCQkJfQoJCX0KCQlTeXN0ZW0ub3V0LnByaW50bG4oeFtuXSk7Cgl9Cn0=

OTg1

985