3. Power Calculus

【题目描述】

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

e.g.

从$x$开始 并重复乘以 $x$，我们可以用三十次乘法计算  $x^{31}$：

$x^2 = x * x，     x^3 = x^2 * x，     x^4 = x^3 * x，     ...，     x^{31} = x^{30} * x。$

这不是计算x 31的最短乘法序列  。有很多方法只有七个乘法。以下是其中之一：

$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。$

但是，无法用更少的乘法来计算  $x^{31}$。因此，这是仅通过乘法计算$x^{31}$的最有效方法之一  。

如果也可以使用除法，我们可以找到较短的操作序列。可以通过六个运算（五个乘法和一个除法）来计算  $x^{31}$：

$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。$

【输入格式】

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

【输出格式】

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

【样例输入】

1
31
70
91
473
512
811
953
0

【样例输出】

0
6
8
9
11
9
13
12

【提示】

请不要打表，请使用搜索，暴力请剪枝（避免卡评测机）

前20%的测试点，测试点组数 <= 100,n <= 100.

前100%的测试点，测试点组数 <= 1000,n <= 1000.

【来源】

luogu & SPOJ