/* ones
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
Given a positive integer N (0<=N<=10000), you are to find an expression equals to N using only 1,+,*,(,). 1 should not appear continuously, i.e. 11+1 is not allowed.
输入
There are multiple test cases. Each case contains only one line containing a integer N
输出
For each case, output the minimal number of 1s you need to get N.
样例输入
2
10
样例输出
2
7
*/
//大意:用1，+, *, (),来组成给定的数N,看最少需要多少个1
//可以列出前20项，就可以看出规律，有的题目就是这样，看不出直接的递推关系，需要列出前几项才能看出来.
#include <iostream>
#include <cmath>
#include <cstdio>
typedef long long ll;
using namespace std;
ll a[10005] = {0, 1, 2, 3, 4, 5};
void fun(){
for(ll i = 6; i <= 10005; i++){
int j;
a[i] = a[i - 1] + 1; //将a[i]值为为较大可能值，就避免了，为质数时又要赋值
for(j = 2; j <= sqrt(i); j++){
if(i % j == 0){
a[i] = min(a[i], a[j] + a[i/j]); //比较前就必须将a[i]置为较大可能数，或者无穷大
// break; //此处不能退出，因为并不是个每个因式分解的都是一样，必须找到最少的值所以要遍历所有的因子
}
}
// if(j > sqrt(i))
// a[i] = a[i - 1] + 1;
}
}
int main(){
ll n;
fun();
while(~scanf("%lld", &n)){
printf("%lld
", a[n]);
}
return 0;
}