#2472. 幂运算

幂运算

Description

xx 开始,反复乘以xx ,可以用3030次乘 法计算x31x^{31}

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

平方运算可以明显地缩短乘法序列,以下是用88次乘法计算x31x^{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 。$

这不是计算x31x^{31} 的最短乘法序列。有很多方法只有77次乘法,以下是其中之一:

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

如果除法也可用,则可以找到一个更短的操作序列。可以用66个运 算(5511除)计算x31x^{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 。$

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

Format

Input

输入是由一行或多行组成的序列,每行都包含一个整数n0<n1000n (0<n ≤1000)。以输入00结束。

Output

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

Samples

1
31
70
91
473
512
811
953
0
0
6
8
9
11
9
13
12

来源

POJ3134