#include <bits/stdc++.h>
using namespace std;
int n,ans;
int a[1008];
bool dfs(int k,int num,int dep){
	if(k>dep||num<0||num*pow(2,dep-k)<n) return 0;		
	if(num==n||num*pow(2,dep-k)==n){
		return 1;
	}
	a[k]=num;
	for(int i=0;i<=k;i++){
		if(dfs(k+1,num+a[i],dep)){
			return 1;
		}
		if(dfs(k+1,num-a[i],dep)){
			return 1;
		}
	}
	return 0;
}
int main(){
    freopen("pourwater.in", "r", stdin);
    freopen("pourwater.out", "w", stdout);		
	while(cin>>n){
		if(n==0){
			break;
		}
        if(n==1){
            cout<<0<<"\n";
            continue;
        }
		a[0]=1;
		int dep=0;
		while(!dfs(0,1,dep)){
			dep++;
		}				
		cout<<dep<<"\n"; 
	} 

	return 0;
}