Let's play a number game. We start with N = 0, and we want to make N = a given integer S.

Only three types of operations are allowed:

1. INC : increment N by 1, i.e. N <-- N + 1
2. DEC : decrement N by 1, i.e. N <-- N - 1
3. DBL : double N, i.e. N <-- 2 N

Of course we want to make N = S with the minimum number of operations. Consider an example: Let S = 7. Then only 5 steps are required, for instance:

1. INC : N = 0 + 1 = 1
2. INC : N = 1 + 1 = 2
3. DBL : N = 2 × 2 = 4
4. DBL : N = 2 × 4 = 8
5. DEC : N = 8 - 1 = 7 <-- DONE!!

Input

Input contains no more than 200 lines. Each line contains one integer S (0 ≤ S ≤ 2³¹). Input is terminated by EOF.

Output

For each S, output the minimum number of operations required to make N = S. You may assume that N is of infinite precision, so NO overflow will ever occur.

Sample Input

7

Sample Output

5