#include<bits/stdc++.h>
using namespace std;
int a[1005];
int dfs(int n,int sum,int k,int d){
	if(k>d) return 0;
	a[k]=sum;
	if(sum<<(d-k)<n) return 0; 
	if(sum==n) return 1; 
	for(int i=1;i<=k;i++){
		if(dfs(n,sum+a[i],k+1,d)) return 1;
		if(dfs(n,sum-a[i],k+1,d)) return 1;
	}
	return 0;  
}
int main(){
	freopen("pow_cal.in","r",stdin);
	freopen("pow_cal.out","w",stdout);
	int n;
	while(cin>>n){
		if(n==0) return 0;
		for(int i=1;;i++){
			if(dfs(n,1,1,i)){ 
				cout<<i-1<<endl;
				break;
			}
		}
	}
	return 0;
}