#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
int n,dep,t[N];
bool dfs (int idx,int sum) {
	if (idx>dep||sum<<(dep-idx)<n) return false;
	if (sum==n||sum<<(dep-idx)==n) return true;
	t[idx]=sum;
	for (int i=0;i<=idx;i++) {
		if (dfs(idx+1,sum+t[i])) return true;
		if (dfs(idx+1,sum-t[i])) return true;
	}
	return false;
}
int main () {
	freopen("pow_cal.in","r",stdin);
	freopen("pow_cal.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	while (cin >> n&&n) {
		for (dep=0;;dep++) {
			if (dfs(0,1)) {
				cout << dep <<"\n";
				break;
			}
		}
	}
	return 0;
}