#include<cstdio>
#define N 1005
using namespace std;
int n,a[N],step;
bool dfs(int now,int t)
{
	if(now>n*2)return 0;
	if((t==step&&now^n)||now<0||(now<<step-t)<n)return 0;
	if(now==n||(now<<step-t)==n)return 1;
	a[t]=now;
	for(int i=0;i<=t;i++)
		if(dfs(now+a[i],t+1))return 1;
		else if(dfs(now-a[i],t+1))return 1;
	return 0;
}
int main(){
	freopen("pow_cal.in","r",stdin);freopen("pow_cal.out","w",stdout);
	while(~scanf("%d",&n))
	{
		if(!n)return 0;
		for(step=0;!dfs(1,0);step++);
		printf("%d\n",step);
	}
	return 0;
}