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

x² = x * x,     x³ = x² * x,     x⁴ = x³ * x,     ...       x³¹ = x³⁰ * x.

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

x² = x * x,     x³ = x² * x,     x⁶ = x³ * x³,     x⁷ = x⁶ * x,     x¹⁴ = x⁷ * x⁷,
x¹⁵ = x¹⁴ * x,     x³⁰ = x¹⁵ * x¹⁵,     x³¹ = x³⁰ * x.

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

x² = x * x,     x⁴ = x² * x²,     x⁸ = x⁴ * x⁴,     x¹⁰ = x⁸ * x²,
x²⁰ = x¹⁰ * x¹⁰,     x³⁰ = x²⁰ * x¹⁰,     x³¹ = x³⁰ * x.

There however is no way to compute x³¹ with fewer multiplications. Thus this is one of the most efficient ways to compute x³¹ only by multiplications.

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

x² = x * x,     x⁴ = x² * x²,     x⁸ = x⁴ * x⁴,     x¹⁶ = x⁸ * x⁸,     x³² = x¹⁶ * x¹⁶,     x³¹ = x³² ÷ x.

This is one of the most efficient ways to compute x³¹ 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 xⁿ by multiplication and division starting with x for the given positive integer n. Products and quotients appearing in the sequence of operations should be x to a positive integer's power. In other 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 xⁿ 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.

Example

Input:
1
31
70
91
473
512
811
953
0

Output: 
0
6
8
9
11
9
13
12