J10 例题-2 幂的运算

题目描述

从 $x$ 开始，反复乘以 $x$ ，我们可以用 $30$ 次乘法计算 $x^{31}$：

$x^2 = x \times x, x^3 = x^2 \times x, x^4 = x^3 \times x, ..., x^{31} = x^{30} \times x$。

平方的操作可以明显缩短乘法的顺序。下面是用 $8$ 次乘法计算 $x^{31}$的方法：

$x^2 = x \times x, x^3 = x^2 \times x, x^6 = x^3 \times x^3, x^7 = x^6 \times x, x^{14} = x^7 \times x^7, x^{15 }= x^{14 } \times x, x^{30 }= x^{15} \times x^{15}, x^{31} = x^{30} \times x$。

这并不是计算 $x^{31}$的最短乘法序列。有许多方法只需要七次乘法。下面是其中之一：

$x^2 = x \times x, x^4 = x^2 \times x^2, x^8 = x^4 \times x^4, x^8 = x^4 \times x^4, x^{10} = x^8 \times x^2, x^{20} = x^{10} \times x^{10}, x^{30} = x^{20} \times x^{10}, x^{31} = x^{30} \times x$。

如果还有除法，我们可以找到一个更短的操作序列。我们可以用六次操作（五次乘法和一次除法）来计算 $x^{31}$：

$x^2 = x \times x, x^4 = x^2 \times x^2, x^8 = x^4 \times x^4, x^{16} = x^8 \times x^8, x^{32} = x^{16} \times x^{16}, x^{31} = x^{32} \div x$。

如果除法和乘法一样快，这是计算 $x^{31}$ 的最有效方法之一。

你的任务是写一个程序，找出最少的操作来计算给定的正整数 $n$ 的乘法和除法，从 $x$ 开始，在序列中出现的积和商应该是 $x$ 到正整数的幂。换句话说，比如说 $x^{-3}$，就不应该出现。

输入格式

输入是一个或多个行的序列，每个行包含一个单一的整数 $n$。输入的结束用一个零表示。

输出格式

你的程序应该打印出从 $x$ 开始计算整数 $n$ 所需的最少的乘法和除法总数。 这些数字应该写在一个单独的行中，没有任何多余的字符，如前导或尾部空格。

样例输入

1
31
70
91
473
512
811
953
0

样例输出

0
6
8
9
11
9
13
12

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据，$1 \le n \le 1000$ 。