/*
	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;
            }
        }
    }
}

LyoKCVRoaXMgc29sdXRpb24gdXNlcyBERlMgYW5kIGl0ZXJhdGl2ZSBkZWVwZW5pbmcsIGEgdGVjaG5pcXVlIHdoZXJlIHdlIHNlYXJjaCBvbmUgbGF5ZXIgZGVlcGVyIGZvciBzb2x1dGlvbnMgaW4gZWFjaCBpdGVyYXRpb24uCiovCgojaW5jbHVkZSA8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbiwgZXhwc1syMF07CmJvb2wgZGZzIChpbnQgZGVwLCBpbnQgbWF4RGVwKSB7CiAgICBpZiAoZGVwID4gbWF4RGVwIHx8IGV4cHNbZGVwXSA8PCAobWF4RGVwIC0gZGVwKSA8IG4pIHJldHVybiBmYWxzZTsKICAgIGlmIChleHBzW2RlcF0gPT0gbikgcmV0dXJuIHRydWU7CiAgICBmb3IgKGludCBpID0gMDsgaSA8PSBkZXA7IGkrKykgewogICAgICAgIGZvciAoaW50IGogOiB7LTEsIDF9KSB7CiAgICAgICAgICAgIGV4cHNbZGVwICsgMV0gPSBleHBzW2RlcF0gKyBqICogZXhwc1tpXTsKICAgICAgICAgICAgaWYgKGV4cHNbZGVwICsgMV0gPiAwICYmIGRmcyhkZXAgKyAxLCBtYXhEZXApKSByZXR1cm4gdHJ1ZTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gZmFsc2U7Cn0KCmludCBtYWluICgpIHsKICAgIHdoaWxlIChjaW4gPj4gbiAmJiBuKSB7ICAgIAogICAgICAgIGZvciAoaW50IGQgPSAwOzsgZCsrKSB7CiAgICAgICAgICAgIGV4cHNbMF0gPSAxOwogICAgICAgICAgICBpZiAoZGZzKDAsIGQpKSB7CiAgICAgICAgICAgICAgICBjb3V0IDw8IGQgPDwgZW5kbDsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9

MQozMQo3MAo5MQo0NzMKNTEyCjgxMQo5NTMKMA==

1
31
70
91
473
512
811
953
0