Problem Description

There is a row of squares on the ground, consisting of $n$ positions. Doraemon is standing on the first square and needs to retrieve something from the $n$-th square.

Doraemon, of course, does not want to run over himself, so he takes out a robot from his pocket! This robot follows the rules below for its movements:

• Initially, the robot is located at the 1st square.
• If the robot is currently at the $x$-th square, it can jump to one of the squares $x-1$, $x+1$, or $2x$ (it is not allowed to jump out of bounds).

The question is, what is the minimum number of jumps the robot needs to reach the $n$-th square?

Input Format

A single line containing a positive integer, representing $n$.

Output Format

A single line containing a positive integer, representing the minimum number of jumps.

Sample Input and Output

Sample Input #1

30

Sample Output #1

6

Sample Input #2

50

Sample Output #2

7

Sample Input #3

64

Sample Output #3

6

Sample Input #4

63

Sample Output #4

8

Notes

Sample Explanation

For the first sample:
$1 \to 2 \to 4 \to 8 \to 16 \to 15 \to 30$

For the second sample:
$1 \to 2 \to 3 \to 6 \to 12 \to 24 \to 25 \to 50$

For the third sample:
$1 \to 2 \to 4 \to 8 \to 16 \to 32 \to 64$

For the fourth sample:
$1 \to 2 \to 4 \to 8 \to 16 \to 32 \to 31 \to 62 \to 63$

Note that in this sample, $63$ cannot be obtained by $64-1$ because the total number of squares is $63$, and there is no $64$-th square.

Data Size and Constraints

For $100\%$ of the data, $1 \leq n \leq 1000000$.

见题面 Input 部分

见题面 Output 部分