#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
int a[MAXN];
int n ,depth = 0;
bool iddfs (int x ,int cur) {
	if (x << (depth - cur) < n) return false;
	if (cur > depth) return false;
	a[cur] = x;
	if (x == n) return true;
	for (int q = 0;q <= cur;++ q) {
		if (iddfs (x + a[q] ,cur + 1)) { return true; }
		if (iddfs (x > a[q] ? x - a[q] : a[q] - x ,cur + 1)) { return true;}
	}
	return false;
}
int main () {
	freopen("mico.in","r",stdin);
	freopen("mico.out","w",stdout);
	while (scanf("%d",&n) && n) {
		depth = 0;
		memset (a ,0 ,sizeof (a));
		while (!iddfs (1 ,0)) {
			memset (a ,0 ,sizeof (a));
			depth ++; }
		printf ("%d\n",depth);
	}
	return 0;
}