#include using namespace std; queue < int > que; int ans[11111]; int n; int solve(int p){ for(int i=0;i<11111;i++) ans[i] = 1<<28; ans[1] = 1; que.push( 1 ); while(!que.empty()){ p = que.front(); que.pop(); int cnt = 0; for(int i=0;i<32;i++) if((p & (1 << i))) cnt++; if(p + cnt <= n){ if(ans[p+cnt] > ans[p]+1){ ans[p+cnt] = ans[p] + 1; que.push( p + cnt ); } } if(p - cnt > 0){ if(ans[p-cnt] > ans[p]+1){ ans[p-cnt] = ans[p] + 1; que.push( p - cnt ); } } } } int main(){ cin >> n; solve(1); if(ans[n] == 1<<28) puts("-1"); else cout << ans[n] << endl; }