/*
	This solution uses DFS and iterative deepening, a technique where we search one layer deeper for solutions in each iteration.
*/

#include <iostream>
using namespace std;

int n, exps[20];
bool dfs (int dep, int maxDep) {
    if (dep > maxDep || exps[dep] << (maxDep - dep) < n) return false;
    if (exps[dep] == n) return true;
    for (int i = 0; i <= dep; i++) {
        for (int j : {-1, 1}) {
            exps[dep + 1] = exps[dep] + j * exps[i];
            if (exps[dep + 1] > 0 && dfs(dep + 1, maxDep)) return true;
        }
    }
    return false;
}

int main () {
    while (cin >> n && n) {    
        for (int d = 0;; d++) {
            exps[0] = 1;
            if (dfs(0, d)) {
                cout << d << endl;
                break;
            }
        }
    }
}