#include<bits/stdc++.h>
using namespace std;

int dep=1;
bool flag;
int n;

int rec[114514];

void dfs(int s,int nx){
	if(s>dep||nx<0){
		return;
	}
	if(flag||nx<<(dep-s)<n){
		return;
	} 
	if(nx<<(dep-s)==n){
		flag=true;
	}
	if(nx==n){
		flag=true;
	}
	rec[s]=nx;
	for(int i=0;i<=s;i++){
		dfs(s+1,nx+rec[i]);
		dfs(s+1,nx-rec[i]);
	}
}

int main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	freopen("pow_cal.in","r",stdin);
	freopen("pow_cal.out","w",stdout); 
	
	while(cin>>n){
		if(n==0){
			return 0;
		}
		dep=0;
		flag=false;
		for(;;dep++){
			dfs(0,1);
			if(flag){
				cout<<dep<<"\n";
				break;
			}
		}
	}
	
	
	
	
	return 0;
}