Problem: Starting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:

x2 = x × x, x3 = x2 × x, x4 = x3 × x, ... , x31 = x30 × x.

The operation of squaring can appreciably shorten the sequence of multiplications. The following is a way to compute x31 with eight multiplications:

x2 = x × x, x3 = x2 × x, x6 = x3 × x3, x7 = x6 × x, x14 = x7 × x7,
x15 = x14 × x, x30 = x15 × x15, x31 = x30 × x.

This is not the shortest sequence of multiplications to compute x31. There are many ways with only seven multiplications. The following is one of them:

x2 = x × x, x4 = x2 × x2, x8 = x4 × x4, x10 = x8 × x2,
x20 = x10 × x10, x30 = x20 × x10, x31 = x30 × x.

There however is no way to compute x31 with fewer multiplications. Thus this is one of the most eficient ways to compute x31 only by multiplications.

If division is also available, we can find a shorter sequence of operations. It is possible to compute x31 with six operations (five multiplications and one division):

x2 = x × x, x4 = x2 × x2, x8 = x4 × x4, x16 = x8 × x8, x32 = x16 × x16,
x31 = x32 ÷ x.

This is one of the most eficient ways to compute x31 if a division is as fast as a multiplication.

Your mission is to write a program to find the least number of operations to compute xn by multiplication and division starting with x for the given positive integer n. Products and quotients appearing in the sequence of operations should be x to a positive integer's power. In other words, x-3, for example, should never appear.



Input

The input is a sequence of one or more lines each containing a single integer n. n is positive and less than or equal to 1000. The end of the input is indicated by a zero.

Output

Your program should print the least total number of multiplications and divisions required to compute xn starting with x for the integer n. The numbers should be written each in a separate line without any superfluous characters such as leading or trailing spaces.

Example

Input

1
31
70
91
473
512
811
953
0


Output

0
6
8
9
11
9
13
12

Solution (in CPP):

Solution:
/*
Power_Calculus
https://onlinejudge.u-aizu.ac.jp/problems/1271
01<= n <= 1000
*/

#include <iostream>
#include <cmath>
#include <algorithm>    // 

using namespace std;

int N; //入力の保持
int dp[10001]; //最初のあたいの保持

/**
 * 再帰関数として深さ優先探索dfsをするメソッド
 * @pram now 現在見ているべき指数
 * @pram isCalced 計算結果を保持する配列
 * @pram depth    深さ
 */
void dfs(int now, int isCalced[15], int depth){

    //もう探索する必要がない
    if(depth == 13) return;

    /**
     * 現在探索している深さまでで、計算結果を取得しているものについて
     * 次(depth+1)計算することができるものを全て探索していく。
     * ex.[1] -> [1, 2] -> [1,2,3], [1,2,4]
     * [1,2] -> 1+2 = 3 -> [1,2,3]
     * [1,2,4] -> 4-1 = 3 -> [1,2,3,4]
     */
    for (int i=0; i <= depth; i ++){
        if(now + isCalced[i] > 10000) continue;

        //すでに求めてあるor未だ求めてないdp[next]より、今探索しているものが小さければ

        //掛け算によって次のものを求める
        if( dp[now + isCalced[i]] >= depth+1){

            dp[now + isCalced[i]] = depth+1;
            
            int nextIsCalced[15];
            for(int k = 0; k <= depth; k++) nextIsCalced[k] = isCalced[k];
            nextIsCalced[depth+1] = now + isCalced[i];

            dfs(now + isCalced[i], nextIsCalced, depth+1);

        }
    }

    for (int i=0; i <= depth; i ++){
        if(now - isCalced[i] <= 0) continue;

        //割り算によって次のものを求める
        if( dp[now - isCalced[i]] >= depth+1){

            dp[now - isCalced[i]] = depth+1;
            
            int nextIsCalced[15];
            for(int k = 0; k <= depth; k++) nextIsCalced[k] = isCalced[k];
            nextIsCalced[depth+1] = now - isCalced[i];

            dfs(now - isCalced[i], nextIsCalced, depth+1);

        }
    }

}

void solve(){

    //dp初期化
    dp[0] = 0; dp[1] = 0;
    for(int i = 2; i<10000; i++) dp[i] = 10000;

    int first_exponent = 1;//最初のべき指数
    int isCalced[15];//計算結果の保持
    int first_depth = 0;//最初の深さ

    isCalced[0] = 1;

    dfs(first_exponent, isCalced, first_depth );

    return;
}

int main(){
    solve();
    while(cin>>N, N!=0) cout<<dp[N]<<endl;
    return 0;
}