（略过没有营养的题干）

题目大意： 给出正整数n,若只能使用乘法或除法，输出使x经过运算（自己乘或除自己，以及乘或除运算过程中产生的中间结果）变成x^n的最少步数

输入格式： 若干行数据，每行一个正整数n，数据以单独成行的0结束

输出格式： 若干行数据，对应每行输入的n所需的步数

Starting with x and repeatedly multiplying by x, we can compute x ^{31}31 with thirty multiplications:

x ^{2}2 = x * x, x ^{3}3 = x ^{2}2 * x, x ^{4}4 = x ^{3}3 * x, ... , x ^{31}31 = x ^{30}30 * x.

The operation of squaring can appreciably shorten the sequence of multiplications. The following is a way to compute x ^{31}31 with eight multiplications:

x ^{2}2 = x * x, x ^{3}3 = x ^{2}2 * x, x ^{6}6 = x ^{3}3 * x ^{3}3 , x ^{7}7 = x ^{6}6 * x, x ^{14}14 = x ^{7}7 * x ^{7}7 ,
x ^{15}15 = x ^{14}14 * x, x ^{30}30 = x ^{15}15 * x ^{15}15 , x ^{31}31 = x ^{30}30 * x.

This is not the shortest sequence of multiplications to compute x ^{31}31 . There are many ways with only seven multiplications. The following is one of them:

x ^{2}2 = x * x, x ^{4}4 = x ^{2}2 * x ^{2}2 , x ^{8}8 = x ^{4}4 * x ^{4}4 , x ^{10}10 = x ^{8}8 * x ^{2}2 ,
x ^{20}20 = x ^{10}10 * x ^{10}10 , x ^{30}30 = x ^{20}20 * x ^{10}10 , x ^{31}31 = x ^{30}30 * x.

There however is no way to compute x ^{31}31 with fewer multiplications. Thus this is one of the most efficient ways to compute x ^{31}31 only by multiplications.

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

x ^{2}2 = x * x, x ^{4}4 = x ^{2}2 * x ^{2}2 , x ^{8}8 = x ^{4}4 * x ^{4}4 , x ^{16}16 = x ^{8}8 * x ^{8}8 , x ^{32}32 = x ^{16}16 * x ^{16}16 , x ^{31}31 = x ^{32}32÷ x.

This is one of the most efficient ways to compute x ^{31}31 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 x ^{n}n 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}−3 , for example, should never appear.

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.

Your program should print the least total number of multiplications and divisions required to compute x ^{n}n 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.

 #include<iostream>

 using namespace std;

 int num[],n,idt;//用num来存储已经创造过的可以用于计算的数，idt是限制的深度

 bool dfs(int step,int now)//step是当前用了多少次运算，now是当前指数

 {

     if(now<=||step>idt||now<<(idt-step)<n) return false;//判断一定不能成功的条件和剪枝

     if(now<<(idt-step)==n) return true;//剪枝

     if(now==n) return true;//如果正确，那么就返回

     num[step]=now;//存储一下这个指数

     for(int i=;i<=step;i++)

     {

         if(dfs(step+,now+num[i])) return true;//乘

         if(dfs(step+,now-num[i])) return true;//除

     }

     return false;//不成功一定要最后返回false

 }

 int main()

 {

     while()

     {

         cin>>n;

         if(n==) break;

         for(idt=;;idt++)//从0开始枚举深度

         if(dfs(,)==true) break;//发现可以就结束循环

         cout<<idt<<endl;

     }

     return ;

 }