#include<bits/stdc++.h>
using namespace std;
int n, dp[14];
int ans;
bool dfs(int x)
{
    if (dp[x] == n) {
        return 1;
    }
    if (x == ans) {
        return 0;
    }
    int tp = dp[0];              
    for (int i = 1; i <= x; i++) {
        tp = max(tp, dp[i]);   
    }
    if ((tp << (ans - x)) >= n) {
        for (int i = x; i >= 0; i--) {
            dp[x + 1] = dp[x] + dp[i];             
            if (dfs(x + 1)) {
                return 1;
            }
            dp[x + 1] = dp[x] - dp[i];             
            if (dfs(x + 1)) {
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    freopen("pow_cal.in", "r", stdin);
    freopen("pow_cal.out", "w", stdout);
    while (1) {
        cin >> n;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            cout << 0 << '\n';
            continue;
        }
        dp[0] = 1;                          
        bool flag = 0;
        for (ans = 1; ans <= 13; ans++) {
            if (dfs(0)) {    
                cout << ans << '\n';
                break;
            }
        }
    }
    return 0;
}