SP7579 YOKOF - Power Calculus

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.