#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
int a[maxn];
int lowbit(int x) {
    return x & -x;
}
int h;
bool dfs(int x,int tot,int cur) {
    if(x << (h - cur) < tot)return false;
    if(cur > h)return false;
    if(x == tot)return true;
    a[cur] = x;
    for(int i = 0;i <= cur;++ i) {
        if(dfs(x + a[i] , tot , cur + 1))return true;
        if(dfs(abs(x - a[i]) , tot , cur + 1))return true;
    }
    a[cur] = 0;
    return false;
}
int solve(int x) {
    h = 0;
    while(!dfs(1 , x , 0))++ h;
    return h;
}
int main() {
    freopen("mico.in","r",stdin);
    freopen("mico.out","w",stdout);
    int x;
    while(~ scanf("%d",&x)) {
        if(!x)break ;
        printf("%d\n",solve(x));
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}