Description

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

$x^2 =x ×x ，x^3 =x^2 ×x ，x^4 =x^3 ×x ，…，x^{31} =x^{30} ×x$

平方运算可以明显地缩短乘法序列，以下是用$8$次乘法计算$x^{31}$的方法：

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

这不是计算$x^{31}$ 的最短乘法序列。有很多方法只有$7$次乘法，以下是其中之一：

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

如果除法也可用，则可以找到一个更短的操作序列。可以用$6$个运 算（$5$乘$1$除）计算$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 。$

如果除法和乘法一样快，则这是计算$x^{31}$ 最有效的方法之一。 编写一个程序，通过从$x$ 开始的乘法和除法，为给定的正整数$n$找 到计算$x^n$ 的最少运算次数。在序列中出现的乘积和商应该是$x$ 的正整 数幂。

Format

Input

输入是由一行或多行组成的序列，每行都包含一个整数$n （0<n ≤1000）$。以输入$0$结束。

Output

单行输出从$x$ 开始计算$x^n$ 所需的最小乘法和除法总数。

Samples

1
31
70
91
473
512
811
953
0

0
6
8
9
11
9
13
12

来源

POJ3134