#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;

struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;

constexpr ll NN = 2e5, M = 1000000007, L = 20;


ll dp[NN];
ll lb(ll x){
    if(dp[x] != -1) return dp[x];
    ll here = __builtin_popcount(x);
    while(x>=2){
        here+=2;
        x/=2;
    }
    return here;
}
ll rec(ll i){
    ll &here = dp[i];
    if(here!=-1) return here;
    here = lb(i);

    //concate
    string s = to_string(i);
    for(int p : rep1(len(s)-1)){
        if(s[p]=='0') continue; //leading zero
        auto s1 = s.substr(0,p);
        auto s2 = s.substr(p);
        ll x = stoll(s1),y=stoll(s2);
        if(lb(x) + lb(y) < here) here=min(rec(x)+rec(y),here);
    }

    //multiply
    for(ll x = 2;x*x<=i;x++){
        if(i%x==0){
            ll y = i/x;
            if(lb(x) + lb(y) < here) here=min(rec(x)+rec(y),here);
        }
    }

    //add
    for(ll x : rep1((i/2))){
        ll y = i-x;
        if(x==0 or y==0) continue;
        if(lb(x) + lb(y) < here) here=min(rec(x)+rec(y),here);
    }

    return here;
}

void run()
{
    int n;
    cin >> n;

    auto ans = rec(n);
    cout << ans << '\n';
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ranges::fill(dp,-1);
    dp[1] = 1;
    // dp[2]=2;
    run();
}