#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { int N; cin >> N; vector load(N + 1, -1); queue q; q.push(1); load[1] = 1; while(!q.empty()) { int p = q.front(); q.pop(); if (p == N) { break; } bitset<14> b(p); int nf = p + (int)b.count(); if (0 < nf && nf <= N && load[nf] == -1) { q.push(nf); load[nf] = load[p] + 1; } int nb = p - (int)b.count(); if (0 < nb && nb <= N && load[nb] == -1) { q.push(nb); load[nb] = load[p] + 1; } } cout << load[N] << endl; return 0; }