#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define RALL(x) (x).rbegin(),(x).rend() #define ALL(x) (x).begin(),(x).end() #define repp(i,n) for(int (i)=1;(i)<=(n);(i)++) #define rep(i,n) for(int (i)=0;(i)<(n);(i)++) #define rev(i,n) for(int (i)=(n-1);(i)>=0;(i)--) #define clr(a) memset((a), 0 ,Nof(a)) #define found(s,e) ((s).find(e)!=(s).end()) typedef pair P; typedef vector > pii; typedef map mdi; #define MAX 9999999 int F(int a){ int cnt=0; while(a>0){ cnt++; a&=a-1; } return cnt; } int main(){ int N; cin >> N; vector dp(N+1,MAX); dp[1]=1; queue qe; qe.push(1); while(!qe.empty()){ int now=qe.front(); qe.pop(); int move=F(now); for(int i= -move; i<=move; i+=move*2){ int next = now+i; if(next<1 || next>N) continue; if(dp[next] != MAX) continue; dp[next] = dp[now]+1; qe.push(next); } } if(dp[N] == MAX) cout << -1 << endl; else cout << dp[N] << endl; return 0; }