Starting with *x* and repeatedly multiplying by *x*, we can compute *x*^{31} with thirty multiplications:*x*^{31} with eight multiplications:*x*^{31}. There are many ways with only seven multiplications. The following is one of them:*x*^{31} with six operations (five multiplications and one division):*x*^{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} by multiplication and division starting with *x* for the given positive integer *n*. Products and quotients appearing in the sequence should be *x* to a positive integer’s power. In others words, *x*^{−3}, for example, should never appear.

The operation of squaring can be appreciably shorten the sequence of multiplications. The following is a way to computex^{2}=x×x,x^{3}=x^{2}×x,x^{4}=x^{3}×x, …,x^{31}=x^{30}×x.

This is not the shortest sequence of multiplications to computex^{2}=x×x,x^{3}=x^{2}×x,x^{6}=x^{3}×x^{3},x^{7}=x^{6}×x,x^{14}=x^{7}×x^{7},x^{15}=x^{14}×x,x^{30}=x^{15}×x^{15},x^{31}=x^{30}×x.

If division is also available, we can find a even shorter sequence of operations. It is possible to computex^{2}=x×x, x^{4}=x^{2}×x^{2},x^{8}=x^{4}×x^{4},x^{8}=x^{4}×x^{4},x^{10}=x^{8}×x^{2},x^{20}=x^{10}×x^{10},x^{30}=x^{20}×x^{10},x^{31}=x^{30}×x.

This is one of the most efficient ways to computex^{2}=x×x,x^{4}=x^{2}×x^{2},x^{8}=x^{4}×x^{4},x^{16}=x^{8}×x^{8},x^{32}=x^{16}×x^{16},x^{31}=x^{32}÷x.

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.

提交代码