#include<bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define drep(x,y,z) for(int x=y;x>=z;x--)
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read()
{
	int x=0;bool flag=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')flag=0;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	if(flag) return x;
	return ~(x-1);
} 
inline void write(int x)
{
	if(x<0) {x=~(x-1);putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
////////////////////////
int ksm[25];
int ans;
inline void ft(){rep(i,0,23) ksm[i]=1<<i;}
inline void solve(int x,int &l,int &r)
{
    l=r=0;
    while(ksm[r]<=x)
    {
        if(ksm[r]==x)
        {
            l=r;
            return;
        }
        r++;
    }
    l=r-1;
    return;
}
int dfs(int x)
{
    int l,r,re;
    solve(x,l,r);
    if(l==r) re=1;
    else re=min(1+dfs(ksm[r]-x),1+dfs(x-ksm[l]));
    return re;
}
int main()
{
    freopen("mico.in","r",stdin);
	freopen("mico.out","w",stdout);
    ft();
    int s1;
    int l,r;
    s1=read();
    while(s1)
    {
        ans=dfs(s1);
        solve(s1,l,r);
        if(l==r) ans=r;
        else ans=min(r+dfs(ksm[r]-s1),l+dfs(s1-ksm[l]));
        cout<<ans<<endl;
        s1=read();
    }
    solve(9,l,r);
    return 0;
}