#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <algorithm> #include <utility> #include <functional> #include <cstring> #include <queue> #include <stack> #include <math.h> #include <iterator> #include <vector> #include <string> #include <set> #include <math.h> #include <iostream> #include<map> #include <iomanip> #include <stdlib.h> #include <list> #include <typeinfo> #include <list> #include <set> using namespace std; #define MAX_MOD 1000000007 #define REP(i,n) for(long long i = 0;i < n;++i) #define LONG_INF 100000000000000 int counter[20000] = {}; int arrive[20000] = {}; int main() { int n; cin >> n; for (int i = 1;i <= 10000;++i) { int tmp = i; int cnt = 0; while (tmp != 0) { cnt += tmp % 2; tmp /= 2; } counter[i] = cnt; } queue<int> gone; gone.push(1); while (gone.empty() == false) { int now = gone.front(); gone.pop(); if (now - counter[now] > 1) { if (arrive[now - counter[now]] == 0 || arrive[now - counter[now]] > arrive[now] + 1) { gone.push(now - counter[now]); arrive[now - counter[now]] = arrive[now] + 1; } } if (now + counter[now] <= n) { if (arrive[now + counter[now]] == 0 || arrive[now + counter[now]] > arrive[now] + 1) { gone.push(now + counter[now]); arrive[now + counter[now]] = arrive[now] + 1; } } } if (arrive[n] == 0&&n != 1) { cout << -1 << endl; return 0; } else cout << arrive[n]+1; return 0; }