#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    while (cin>>n) {
        vector<unsigned> v(n+10, -1);
        v[1]=1;
        bool changed=true;
        while (changed) {
            changed=false;
            for(int i=1;i<=n;++i) if (v[i]!=-1) {
                int k=__builtin_popcount(i);
                if (v[i+k]>v[i]+1) {
                    v[i+k]=v[i]+1;
                    changed=true;
                }
                if (v[i-k]>v[i]+1) {
                    v[i-k]=v[i]+1;
                    changed=true;
                }
            }
        }
        cout<<(int)v[n]<<endl;
    }
}