#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;

using _loop_int = int;
#define REP(i,n) for(_loop_int i=0; i<(_loop_int)(n); i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a); i<(_loop_int)(b); i++)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1; i>=(_loop_int)(a); i--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))
#define ALL(v) (v).begin(),(v).end()

#define DEBUG(x) cerr<<#x<<": "<<(x)<<endl
#define DEBUG_VEC(v) cerr<<#v<<": ";REP(__i,(v).size())cerr<<((v)[__i])<<", ";cerr<<endl

const ll MOD = 1000000007ll;

const int MAX = 1000;
const int LIM = 13;
int ans[MAX+1] = {
    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,
};
using State = pair<int,vi>;

set<State> memo;

void dfs(const State& st){
    int dist = st.first + 1;
    if(dist >= LIM)return;
    // if(memo.count(st))return;
    // memo.insert(st);
    vi cand = st.second;
    int n = cand.size();

    set<int> used;
    REP(i,n)REP(j,i+1){
        int y = cand[i] - cand[j];
        if(used.count(y) == 0 && find(ALL(cand),y) == cand.end() && i==n-1){
            used.insert(y);
            if(y <= MAX)CHMIN(ans[y], dist);
            if(dist+1 != LIM){
                vi ncand(n+1);
                REP(k,n)ncand[k] = cand[k];
                ncand[n] = y;
                sort(ALL(ncand));
                State nstate(dist, ncand);
                dfs(nstate);
            }
        }
        int x = cand[i] + cand[j];
        if(used.count(x) == 0 && find(ALL(cand),x) == cand.end() && x > cand.back()){
            used.insert(x);
            if(x <= MAX)CHMIN(ans[x], dist);
            if(dist+1 != LIM){
                vi ncand(n+1);
                REP(k,n)ncand[k] = cand[k];
                ncand[n] = x;
                sort(ALL(ncand));
                State nstate(dist, ncand);
                dfs(nstate);
            }
        }
    }
}

int main(){
    // // precalc
    // fill(ans,ans+MAX+1,LIM);
    // ans[0] = 0;
    // ans[1] = 0;
    // State init(0,vi(1,1));
    // dfs(init);

    // // output
    // FOR(i,0,MAX+1){
    //     printf("%d,",ans[i]);
    //     if(i%100==0)puts("");
    // }

    // query
    while(true){
        int n;
        cin>>n;
        if(n==0)break;
        int ret = ans[n];
        cout<<ret<<endl;
    }
    return 0;
}



Measured memory_bytes: 3024