Minimum Steps to Target

You are given a positive integer \(n\). Your task is to determine the minimum number of operations required to transform the number 1 into \(n\) using the following operations:

• Multiply the current number by 2.
• Subtract 1 from the current number.

You are guaranteed that it is always possible to reach \(n\) starting from 1. Formally, if you define \(f(n)\) as the minimum number of operations required for this transformation, then for \(n = 1\), \(f(1) = 0\); for \(n > 1\), a valid recurrence when processing backwards is:

\[ f(n) = \begin{cases} 1 + f\Bigl(\frac{n}{2}\Bigr) & \text{if } n \text{ is even},\\ 1 + f(n-1) & \text{if } n \text{ is odd}. \end{cases} \]

Input Format: A single line containing a positive integer \(n\).

Output Format: A single integer representing the minimum number of operations required to reach \(n\) from 1.

Examples:

Input: 3
Output: 2
Input: 10
Output: 4

</p>

inputFormat

The input consists of a single line containing a positive integer (n) (1 (\leq n \leq 10^{9})).

outputFormat

Output a single integer which is the minimum number of operations required to transform 1 into (n) using the allowed operations.## sample

1

0