#include <bits/stdc++.h>

using namespace std;

namespace {

    const int MAX_N = 1000;

    int N;
    bool input() {
        cin >> N;
        return N != 0;
    }

    int ans[1000] = {
              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
    };

    void solve() {
        cout << ans[N - 1] << endl;
    }
}

int main() {
    while (input()) solve();
    return 0;
}

Measured memory_bytes: 1164