#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>

#define repi(n) for (int i=0;i<n;i++)
#define repj(n) for (int j=0;j<n;j++)
#define repk(n) for (int k=0;k<n;k++)
#define pb(x) push_back(x)
#define pause() system("pause");
#define MAXN 1024

using namespace std;

int a[MAXN];
int s[MAXN];
vector<int> b;
int k;

int solve(int p);

void init() {
     scanf("%d",&k);
     s[0]=0;
     s[1]=0;
     s[2]=1;
}

void erato() {
     for (int i=2;i<MAXN;i++)
         if (!a[i]) {
            for (int j=2*i;j<MAXN;j+=i)
                a[j]=1;
            b.pb(i);
            }     
}

int break_down(int cu,int st,int ans) {
    ans+=solve(st-1);
    if (cu==1) { return ans;}
    int minans=2<<20;
    for (int i=0;b[i]<=cu;i++)
        if (!(cu%b[i])) {
           int cur=1+break_down((cu/b[i]),b[i],ans);
           if (cur<minans) minans=cur;
           }
    return minans;
}

int solve(int p) {
    int minans=2<<20;
    if (s[p]!=0) return s[p];
    else if (p==1) return 0;
    for (int i=0;b[i]<=p;i++)
        if (!(p%b[i])) {
           int cur=1+break_down((p/b[i]),b[i],0);
           if (cur<minans) minans=cur;
           }
    s[p]=minans;
    return minans;
}

void print() {
     int ans=solve(k);
     printf("%d\n",ans);
}

int main() {
    init();
    erato();
    print();
return 0;
}
