    #include <cstdio>
     
    #define MAX_N 1024
    #define MAX_D 20
    int exp[MAX_D] = {1}, ans[MAX_N];
     
    void dfs(int d)
    {
        if (d > MAX_D)
        {
            return;
        }
        for (int i = 0; i <= d; i++)
        {
            exp[d + 1] = exp[i] + exp[d]; // 乘法
            if (exp[d + 1] < MAX_N && ans[exp[d + 1]] >= d + 1)
            {
                ans[exp[d + 1]] = d + 1;
                dfs(d + 1);
            }
            exp[d + 1] = exp[d] - exp[i]; // 除法
            if (exp[d + 1] > 0 && ans[exp[d + 1]] >= d + 1)
            {
                ans[exp[d + 1]] = d + 1;
                dfs(d + 1);
            }
        }
    }
     
    int main()
    {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
        for (int i = 2; i < MAX_N; i++)
        {
            //每个n的上界=除法+乘法
            ans[i] = __builtin_popcount(i) + (30 - __builtin_clz(i));
        }
        dfs(0);
     
        int n;
        while (~scanf("%d", &n), n)
        {
            printf("%d\n", ans[n]);
        }
    #ifndef ONLINE_JUDGE
        fclose(stdin);
    #endif
        return 0;
    }
