#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    int n;
    cin>>n;
    int inf = 1e9;
    vector<int> dp(n+1,inf);
    dp[1] = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j*i<=n;j++){
            int ni = i * j;
            if(n%ni!=0) continue;
            dp[ni] = min(dp[ni],dp[i]+j);
        }
    }
    cout<<dp[n]<<endl;
}