#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
int a[40],n,k,flag;
void dfs(int x){
	if(x==k+1){
		if(a[k]==n){
			
			flag=1;
			return;
		}else{
			return;
		}
	}else{
		int t[1050];
		for(int i=0;i<=1024;i++)t[i]=0;
		for(int i=1;i<x;i++){
			if(a[x-1]+a[i]<=1024)t[a[x-1]+a[i]]=1;
			if(a[x-1]-a[i]>=0)t[a[x-1]-a[i]]=1;
		}
		for(int i=1;i<x;i++)t[a[i]]=0;
		for(int i=0;i<=1024;i++){
			if(t[i]){
				a[x]=i;
				dfs(x+1);
				a[x]=0;
			}
		}
	}
}
void work(){
	if(n==1){
		printf("1\n");
		return;
	}
	a[1]=1;flag=0;
	if(n<=100){
		for(int i=1;i<=15;i++){
			k=i;
			dfs(2);
			if(flag)break;
		}
		cout<<k-1<<endl;
	}else if(n<=200){
		for(int i=2;i<=5;i++)a[i]=a[i-1]*2;
		for(int i=5;i<=15;i++){
			k=i;
			dfs(6);
			if(flag)break;
		}
		cout<<k-1<<endl;
	}else if(n<=300){
		for(int i=2;i<=6;i++)a[i]=a[i-1]*2;
		for(int i=6;i<=15;i++){
			k=i;
			dfs(7);
			if(flag)break;
		}
		cout<<k-1<<endl;
	}else if(n<=500){
		for(int i=2;i<=7;i++)a[i]=a[i-1]*2;
		for(int i=7;i<=15;i++){
			k=i;
			dfs(8);
			if(flag)break;
		}
		cout<<k-1<<endl;
	}else{
		for(int i=2;i<=8;i++)a[i]=a[i-1]*2;
		for(int i=8;i<=15;i++){
			k=i;
			dfs(9);
			if(flag)break;
		}
		cout<<k-1<<endl;
	}
	return;
}
int main(){
	freopen("pow_cal.in","r",stdin);
	freopen("pow_cal.out","w",stdout);
	while(cin>>n&&n)work();
	return 0;
}