#include<bits/stdc++.h>
using namespace std;
int m,n,sk[100];
int dfs(int p,int s){
	if(p>m)return s==n;
    if(s<<(m-p+1)<n)return 0;
	sk[p]=s;
	for(int i=1;i<=p;i++)
		if(dfs(p+1,s-sk[i])||dfs(p+1,s+sk[i])) return 1;
	return 0;
}
int  main()
{
    freopen("pow_cal.in","r",stdin);	
    freopen("pow_cal.out","w",stdout);
   while(cin>>n&&n)
   {
       while(!dfs(1,1))
       m++;
       cout<<m<<endl;m=0;
   }
    return 0;
}