#include<bits/stdc++.h>
using namespace std;
int num[100001], n, dep;
bool dfs(int step,int now){
    if(now <= 0 || step > dep || now << (dep - step) < n) return 0;
    if(now << (dep - now) == n) return 1;
    if(now == n) return 1;
    num[step] = now;
    for(int i = 0;i <= step; i++){
        if(dfs(step + 1,now + num[i])) return 1;
        if(dfs(step + 1,now - num[i])) return 1;

    }
    return 0;
}

int main(){
    freopen("pow_cal.in", "r", stdin);
    freopen("pow_cal.out", "w", stdout);
    while(1){
        cin >> n;
        if(n == 0) break;
        for(dep = 0; ; dep++){
            if(dfs(0,1)) break;
        }
        cout << dep << endl;
    }
    return 0;
}