#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1010;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<48||c>57){
		if(x==45) f=-1;
		c=getchar();
	}
	while(c>=48&&c<=57){
		x=x*10+c-48;
		c=getchar();
	}
	return f*x;
}
int n;
int dep;
int s[N];
bool dfs(int step,int x){
	if(step>dep)  return 0;
	//x*(2^(dep-step))
	if(x<=0||x<<(dep-step)<n) return 0;
	if(x==n||x<<(dep-step)==n) return 1;
	s[step]=x;
	for(int i=0;i<=step;i++){
		if(dfs(step+1,x+s[i])) return 1;
		if(dfs(step+1,x-s[i])) return 1;
	}
	return 0;
}
int main(){
	freopen("pow_cal.in","r",stdin);
	freopen("pow_cal.out","w",stdout);
	while(1){
		n=read();
		if(n==0) break;
		for(dep=0;;dep++){
			if(dfs(0,1)) break;
		}
		printf("%d\n",dep);
	}
	return 0;
}