从 x 开始，反复乘以 x ，我们可以用30次乘法计算得到x31：
x2=x×x，x3=x2×x，x4=x3×x，…，x31=x30×x。
平方运算可以明显缩短乘法的计算次数。以下是8次计算得到x31的算法：
x2=x×x，x3=x2×x，x6=x3×x3，x7=x6×x，x14=x7×x7，x15=x14×x，x30=x15×x15，x31=x30×x。
这不是计算x31的最快方法。实际上有多种方法可以用7步运算得到结果。以下方法是其中之一：
x2=x×x，x4=x2×x2，x8=x4×x4，x10=x8×x2，x20=x10×x10，x30=x20×x10，x31=x30×x。
如果可以用除法，我们会发现有步数更少的方法计算出结果，比如：可以用六步运算（五次乘一次除）计算x31：
x2=x×x，x4=x2×x2，x8=x4×x4，x16=x8×x8，x32=x16×x16，x31=x32÷x。
这是计算x31最有效的方法之一。
你的任务是编写一个程序，通过对给定的正整数n进行从x开始的乘法和除法运算，找到计算出xn的最少运算次数。计算中出现的乘和除的值应该是x的正整数幂。换句话说，x−3不应该出现。
输入包含一个或多个测试数据（不超过20组），每行包含一个整数n。n为正整数且小于或等于1000，输入0表示测试数据的读入结束。
输出计算到xn所需的最小乘法或除法计算总次数，每个输出占1行。
1 31 70 91 473 512 811 953 0
0 6 8 9 11 9 13 12
POJ