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