#include<bits/stdc++.h>
using namespace std;
int n, d, a[6010];
int dfs(int x, int c) {
	if(x << (d - c) < n) {
		return 0;
	}
	if(c > d) {
		return 0;
	}
	a[c] = x;
	if(x == n) {
		return 1;
	}
	for(int i = 0; i <= c; ++ i) {
		if(dfs(x + a[i], c + 1)) {
			return 1;
		}
		if(dfs(abs(x - a[i]), c + 1)) {
			return 1;
		}
	}
	return 0;
}
int main () {
	freopen("mico.in","r",stdin);
	freopen("mico.out","w",stdout);
	
	while (scanf("%d",&n) && n) {
		d = 0;
		memset(a, 0, sizeof(a));
		while(!dfs(1, 0)) {
			memset (a, 0, sizeof(a));
			d ++;
		}
		printf("%d\n", d);
	}
	return 0;
}