Problem E: PIPI算指数

Problem E: PIPI算指数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 248  Solved: 63
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI刚学完乘除法,他想知道经过多少次乘除法可以将 x 变为 xn, 如当 n = 31 时,需要六次变换可以从 x -> x31.
x2 = x*x, x4 = x2*x2 ,x8 = x4*x4,x16 = x8*x8,x32=x16*x16,x31 = x32/x。
计算过程可以用 x 之前的算出的结果(比如说算最后一步可以用 x ,x2,x4,x8,x16,x32),并且 x 的指数总是正整数。

Input

输入包含多组测试用例。
对于每一组测试用例,输入包含一个正整数 n (1<=n<=1000)
以一个单独的0代表输入结束。

Output

对于每组测试用例,输出最少需要的步数。

Sample Input

1
31
70
0

Sample Output

0
6
8