题目描述

从 $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}$ 的最快方法。实际上有多种方法可以用 $7$ 步运算得到结果。以下方法是其中之一：

$x^2=x \times x$ ， $x^4=x^2 \times x^2$ ， $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^n$ 的最少运算次数。计算中出现的乘和除的值应该是 $x$ 的正整数幂。换句话说， $x^{−3}$ 不应该出现。

输入

输入包含一个或多个测试数据（不超过 $20$ 组），每行包含一个整数 $n$ 。

$n$ 为正整数且小于或等于 $1000$ ，输入 $0$ 表示测试数据的读入结束。

输出

输出计算到 $x$^$n$ 所需的最小乘法或除法计算总次数，每个输出占 $1$ 行。

样例

1
31
70
91
473
512
811
953
0

0
6
8
9
11
9
13
12

来源

POJ