Question
Shift Snap
Alice starts with an integer B = 1. In one move, he can either subtract 1 from B, making it B - 1, or double B. Determine the minimum number of moves needed to transform B into M.
Input
The first and only line of the input contains an integer M.
Constraints
1 ≤ M ≤ 109
Constraints
1 ≤ M ≤ 109
Output
Print the minimum number of moves required to convert B to M.
Example
Sample Input
10
Sample Output
6
Explanation
First we multiply 1 by 2, B = 2.
Then we again multiply it by 2, B = 4
Now, we decrement it once, B = 3
Now, we multiply it by 2, B = 6
Now we decrement it once, B = 5
And finally, we multiply it by 2, B = 10.
10
Sample Output
6
Explanation
First we multiply 1 by 2, B = 2.
Then we again multiply it by 2, B = 4
Now, we decrement it once, B = 3
Now, we multiply it by 2, B = 6
Now we decrement it once, B = 5
And finally, we multiply it by 2, B = 10.