#include<bits/stdc++.h>
using namespace std;
int n;
int a[1010];
int dep;

bool dfs(int x, int step)
{
if(step > dep)          return false;
if(x << (dep - step) < n)return false;
if(x == n)return true;
a[step] = x;
for(int i = 0; i <= step; i++)
{
if(dfs( x + a[i] ,step+1))return true;
if(dfs( abs(x-a[i]) ,step+1))return true;		
}
return false;
}

int main()
{
    freopen("mico.in","r",stdin);
    freopen("mico.out","w",stdout);
while(scanf("%d", &n) && (n != 0) )
{
dep = 0;
memset(a, 0, sizeof(a));	
while(!dfs(1, 0))
{
dep++;	
memset(a, 0, sizeof(a));
}
cout << dep << endl;	
}

return 0;
}