#include "bits/stdc++.h"

#define int long long
#define REP(i,a,n) for(int i=a;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define REV(i,a,n) for(int i=n;i>=a;--i)
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define show(n) cerr<<#n<<" = "<<n<<endl
#define showp(n) cerr<<n.fs<<", "<<n.sc<<endl
#define shows(n) for(auto z:n){cerr<<z<<", ";}cerr<<endl
#define showsp(n) for(auto z:n){cerr<<z.fs<<" "<<z.sc<<", "}cerr<<endl

#define yes puts("Yes")
#define no puts("No")
#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

const int INF=1LL<<55;
const int MOD=1000000007;

bool state[1001];
vi ans(1001);
int target;


void dfs(int depth, int pre, int maxv ){
  if ( pre == target ){
    ans[target] = min( ans[target], depth );
    return;
  }
  if ( depth >= ans[target] ) return;
  
  int next, d = 0, p = maxv;
  
  while( p < target ){d++; p *= 2;}
  if ( depth + d >= ans[target] ) return;
  
  for ( int i = 1; i <= maxv; i++ ){
    if ( !state[i] ) continue;
    next = pre + i;
    if ( next <= 1000 && !state[next] ){
      state[next] = true;
      dfs(depth+1, next, max(maxv, next));
      state[next] = false;
    }
    next = ( pre > i ) ? ( pre - i ) : (i - pre);
    if ( !state[next] ){
      state[next] = true;
      dfs(depth+1, next, max(maxv, next));
      state[next] = false;
    }
  }
}

void solve(){
    for(int i=0;i<=1000;i++) state[i]=false;
    state[1]=true;
    dfs(0,1,1);
    cout<<ans[target]<<endl;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    fill(all(ans),13);
    while(cin>>target,target){
        solve();
    }

    return 0;
}
