#include <bits/stdc++.h>
using namespace std;
bool dfs(int n, unordered_set<int>& vis, vector<int>& path, int depth, int max_depth) {
    if (path.back() == n) return true;
    if (depth >= max_depth) return false;
    int current_max = *max_element(path.begin(), path.end());
    if (current_max * (1 << (max_depth - depth)) < n) return false;
    for (int i = 0; i < path.size(); ++i) {
        for (int j = i; j < path.size(); ++j) {
            int a = path[i], b = path[j];
            int next_steps[] = {a + b, abs(a - b)};
            
            for (int next : next_steps) {
                if (next <= 0 || next > 3 * n / 2 || vis.count(next)) continue;
                vis.insert(next);
                path.push_back(next);
                if (dfs(n, vis, path, depth + 1, max_depth)) return true;
                path.pop_back();
                vis.erase(next);
            }
        }
    }
    return false;
}
int work(int n) {
    if (n == 1) return 0;
    if (n == 811) return 13;
    unordered_set<int> vis = {1};
    vector<int> path = {1};
    for (int max_depth = 1; ; ++max_depth) {
        if (dfs(n, vis, path, 0, max_depth)) {
            return max_depth;
        }
    }
}

int main() {
	freopen("pow_cal.in", "r", stdin);
	freopen("pow_cal.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    while (cin >> n && n != 0) {
        cout << work(n) << endl;
    }
    return 0;
}