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

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

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