#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    int bit_pop[10010] = {};
    for (int i = 1; i <= N; ++i) {
        bit_pop[i] = bitset<20>(i).count();
    }

    int dp[10010] = {};
    for (int i = 1; i <= N; i++)
        dp[i] = 11111;
    dp[1] = 1;
    queue<int> que;
    que.push(1);
    while (!que.empty()) {
        int now = que.front();
        que.pop();
        int nxt;
        nxt = now - bit_pop[now];
        if (nxt >= 1 && dp[nxt] == 11111) {
            dp[nxt] = dp[now] + 1;
            que.push(nxt);
        }
        nxt = now + bit_pop[now];
        if (nxt <= N && dp[nxt] == 11111) {
            dp[nxt] = dp[now] + 1;
            que.push(nxt);
        }
    }
    if (dp[N] == 11111)
        dp[N] = -1;
    cout << dp[N] << endl;
}