#include<iostream>
using namespace std;

const int MAX = 1001;
const int NMAX = 1001;
const int LIM = 13;
const int inf = 1<<26;

/*

  x x = x^2
  x^2 x = x^3
  x^2 x^2 = x^4
  x^4 x^3? = x^7
  
  1 2 4 8 16 32 1 : 31(7)
  1 2 4 : 7(3?)
  

  31 = 16 + 15
  15 = 8 + 7 
  7 = 4 + 3 4
  3 = 2 + 1 2
  2 = 1 + 1 1
  
 */

bool generated[MAX];
int res[MAX];
int goal;

void solve(int cur, int depth)
{
  res[cur] = min(res[cur], depth);
  if( cur == goal ){
    res[goal] = min( res[goal], depth );
    return ;
  }

  int max_pred = 1;
  int pred1 = 1, pred2 = 1;
  int tcur = cur;
  while(true){
    if((tcur<<1)>goal)break;
    tcur<<=1;
    ++pred1;
  }
  tcur = cur;
  while(true){
    if((tcur>>1)<goal)break;
    tcur>>=1;
    ++pred2;
  }
  max_pred = max( pred1, pred2 );
  
  if( max_pred+depth > res[goal] ) return ;
  if( max_pred+res[cur] > res[goal] ) return ;
  if( max_pred+depth > LIM ) return ;
  
  for(int i = 1; i <= MAX; ++i){
    if( !generated[i] ) continue;

    if( cur+i < MAX && !generated[cur+i] ){
      generated[cur+i]=true;
      solve(cur+i,depth+1);
      generated[cur+i]=false;
    }

    if( cur-i >  0  && !generated[cur-i] ){
      generated[cur-i]=true;
      solve(cur-i,depth+1);
      generated[cur-i]=false;
    }

    if( i-cur >  0  && !generated[i-cur] ){
      generated[i-cur]=true;
      solve(i-cur,depth+1);
      generated[i-cur]=false;
    }
  }
  
}

//-------------------------
// emb
//-------------------------
const int ans[1001] = {0,0,1,2,2,3,3,4,3,4,
4,5,4,5,5,5,4,5,5,6,
5,6,6,6,5,6,6,6,6,7,
6,6,5,6,6,7,6,7,7,7,
6,7,7,7,7,7,7,7,6,7,
7,7,7,8,7,8,7,8,8,8,
7,8,7,7,6,7,7,8,7,8,
8,8,7,8,8,8,8,8,8,8,
7,8,8,8,8,8,8,9,8,9,
8,9,8,8,8,8,7,8,8,8,
8,9,8,9,8,9,9,9,8,9,
9,9,8,9,9,9,9,9,9,9,
8,9,9,9,8,9,8,8,7,8,
8,9,8,9,9,9,8,9,9,9,
9,9,9,9,8,9,9,9,9,9,
9,10,9,9,9,9,9,9,9,9,
8,9,9,9,9,9,9,10,9,10,
9,10,9,10,10,10,9,10,10,10,
9,10,10,10,9,10,9,10,9,9,
9,9,8,9,9,9,9,10,9,10,
9,10,10,10,9,10,10,10,9,10,
10,10,10,10,10,10,9,10,10,10,
10,10,10,10,9,10,10,10,10,10,
10,10,10,10,10,10,10,10,10,10,
9,10,10,10,10,10,10,10,9,10,
10,10,9,10,9,9,8,9,9,10,
9,10,10,10,9,10,10,11,10,11,
10,10,9,10,10,11,10,11,10,10,
10,10,10,10,10,10,10,10,9,10,
10,10,10,10,10,11,10,10,10,11,
10,11,11,11,10,11,10,11,10,11,
10,11,10,11,10,10,10,10,10,10,
9,10,10,10,10,10,10,11,10,11,
10,11,10,11,11,11,10,11,11,11,
10,11,11,11,10,11,11,11,11,11,
11,11,10,11,11,11,11,11,11,11,
10,11,11,11,11,11,11,11,10,11,
11,11,10,11,11,11,10,11,10,11,
10,10,10,10,9,10,10,10,10,11,
10,11,10,11,11,11,10,11,11,11,
10,11,11,11,11,11,11,11,10,11,
11,11,11,11,11,11,10,11,11,11,
11,11,11,11,11,11,11,11,11,11,
11,11,10,11,11,11,11,11,11,11,
11,11,11,11,11,11,11,11,10,11,
11,11,11,11,11,11,11,11,11,11,
11,12,11,12,11,11,11,12,11,12,
11,11,11,11,11,11,11,11,11,11,
10,11,11,11,11,11,11,11,11,11,
11,12,11,12,11,11,10,11,11,12,
11,12,11,11,10,11,11,11,10,11,
10,10,9,10,10,11,10,11,11,11,
10,11,11,12,11,12,11,11,10,11,
11,12,11,12,12,11,11,12,12,12,
11,12,11,11,10,11,11,12,11,12,
12,12,11,11,12,12,11,12,11,12,
11,11,11,12,11,12,11,11,11,12,
11,11,11,11,11,11,10,11,11,11,
11,11,11,12,11,11,11,12,11,12,
12,12,11,12,11,12,11,12,12,12,
11,12,12,12,12,12,12,12,11,12,
12,12,11,12,12,12,11,12,12,12,
11,12,12,12,11,12,12,12,11,12,
11,12,11,12,11,11,11,11,11,11,
10,11,11,11,11,11,11,12,11,12,
11,12,11,12,12,12,11,12,12,12,
11,12,12,12,11,12,12,12,12,12,
12,12,11,12,12,12,12,12,12,12,
11,12,12,12,12,12,12,12,11,12,
12,12,12,12,12,12,12,12,12,12,
12,12,12,12,11,12,12,12,12,12,
12,12,12,12,12,12,12,12,12,12,
11,12,12,12,12,12,12,12,12,12,
12,12,12,12,12,12,11,12,12,12,
12,12,12,12,11,12,12,12,12,12,
12,12,11,12,12,12,11,12,12,12,
11,12,11,12,11,11,11,11,10,11,
11,11,11,12,11,12,11,12,12,12,
11,12,12,12,11,12,12,12,12,12,
12,12,11,12,12,12,12,12,12,12,
11,12,12,12,12,12,12,12,12,12,
12,13,12,12,12,12,11,12,12,12,
12,13,12,12,12,12,12,12,12,12,
12,12,11,12,12,12,12,12,12,12,
12,12,12,12,12,12,12,13,12,12,
12,13,12,13,12,12,12,13,12,12,
12,12,12,12,11,12,12,12,12,12,
12,13,12,12,12,13,12,13,12,12,
12,13,12,13,12,13,12,12,12,12,
12,12,12,12,12,12,11,12,12,12,
12,12,12,12,12,12,12,13,12,13,
12,13,12,13,12,13,12,13,12,13,
12,13,13,13,12,13,13,13,12,13,
12,13,12,13,13,13,12,13,13,13,
12,13,12,13,12,12,12,13,12,13,
12,12,12,12,12,12,12,12,12,12,
11,12,12,12,12,12,12,12,12,12,
12,13,12,13,12,12,12,12,12,13,
12,13,13,13,12,13,13,13,12,13,
12,12,11,12,12,13,12,13,13,13,
12};
int main()
{
  /*
  for(int i = 0; i < MAX; ++i){
    res[i] = inf;
    generated[i] = false;
  }
  generated[1] = true;
  while(true){
    cin >> goal;
    if( goal == 0 ) break;
    
    solve(1,0);
    cout << goal << ' ' << res[goal] << endl;
  }
  */
  /*
  cout << "const int ans[1001] = {0";
  for(int i = 1; i < NMAX; ++i){
    cout << "," << res[i];
  }
  cout << "};" << endl;
  */

  while(true){
    cin >> goal;
    if( goal == 0 ) break;
    cout << ans[goal] << endl;
  }
  
  return 0;
}

Measured memory_bytes: 0