Description

Starting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:

x2 = x  x, x3 = x2  x, x4 = x3  x, , x31 = x30  x.

The operation of squaring can be appreciably shorten the sequence of multiplications. The following is a way to compute x31 with eight multiplications:

x2 = x  x, x3 = x2  x, x6 = x3  x3, x7 = x6  x, x14 = x7  x7, x15 = x14  x, x30 = x15  x15, x31 = x30  x.

This is not the shortest sequence of multiplications to compute x31. There are many ways with only seven multiplications. The following is one of them:

x2 = x  x, x4 = x2  x2, x8 = x4  x4, x8 = x4  x4, x10 = x8  x2, x20 = x10  x10, x30 = x20  x10, x31 = x30  x.

If division is also available, we can find a even shorter sequence of operations. It is possible to compute x31 with six operations (five multiplications and one division):

x2 = x  x, x4 = x2  x2, x8 = x4  x4, x16 = x8  x8, x32 = x16  x16, x31 = x32  x.

This is one of the most efficient ways to compute x31 if a division is as fast as a multiplication.

Your mission is to write a program to find the least number of operations to compute xn by multiplication and division starting with x for the given positive integer n. 
Products and quotients appearing in the sequence should be x to a positive integers power. In others words, x?3, for example, should never appear.

Input

The input is a sequence of one or more lines each containing a single integer n. n is positive and less than or equal to 1000. 
The end of the input is indicated by a zero.

Output

Your program should print the least total number of multiplications and divisions required to compute xn starting with x for the integer n.
 The numbers should be written each in a separate line without any superfluous characters such as leading or trailing spaces.

Sample Input

1
31
70
91
473
512
811
953
0

Sample Output

0
6
8
9
11
9
13
12

Hint


Author

Source