YOKOF - Power Calculus

题意翻译

(略过没有营养的题干) **题目大意**: 给出正整数n,若只能使用乘法或除法,输出使x经过运算(自己乘或除自己,以及乘或除运算过程中产生的中间结果)变成x^n的最少步数 ***输入格式***: 若干行数据,每行一个正整数n,数据以单独成行的0结束 ***输出格式***: 若干行数据,对应每行输入的n所需的步数

题目描述

Starting with _x_ and repeatedly multiplying by _x_, we can compute _x_ $ ^{31} $ with thirty multiplications: > _x_ $ ^{2} $ = _x_ \* _x_, _x_ $ ^{3} $ = _x_ $ ^{2} $ \* _x_, _x_ $ ^{4} $ = _x_ $ ^{3} $ \* _x_, ... , _x_ $ ^{31} $ = _x_ $ ^{30} $ \* _x_. The operation of squaring can appreciably shorten the sequence of multiplications. The following is a way to compute _x_ $ ^{31} $ with eight multiplications: > _x_ $ ^{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_. This is not the shortest sequence of multiplications to compute _x_ $ ^{31} $ . There are many ways with only seven multiplications. The following is one of them: > _x_ $ ^{2} $ = _x_ \* _x_, _x_ $ ^{4} $ = _x_ $ ^{2} $ \* _x_ $ ^{2} $ , _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_. There however is no way to compute _x_ $ ^{31} $ with fewer multiplications. Thus this is one of the most efficient ways to compute _x_ $ ^{31} $ only by multiplications. If division is also available, we can find a shorter sequence of operations. It is possible to compute _x_ $ ^{31} $ with six operations (five multiplications and one division): > _x_ $ ^{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_. This is one of the most efficient ways to compute _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 of operations should be _x_ to a positive integer's power. In other words, _x_ $ ^{-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} $ 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.

输入输出样例

输入样例 #1

1
31
70
91
473
512
811
953
0

输出样例 #1

0
6
8
9
11
9
13
12