Problem Description

Friends of Cossack Moustache received that secret letter. It turned out that inside there was a blueprint for a pair of ancient magic shoes. These magic shoes allow the wearer to accelerate to an amazing speed. The wearer’s initial speed is $1$ meter per second.

If the current speed of the person wearing the magic shoes is $a$ meters per second, then she can cast one of the following two spells:

• Increase her speed by $a$ meters per second.
• Increase her speed by $a+1$ meters per second.

What is the minimum number of spells she needs to cast to increase her speed exactly to $k$ meters per second?

Input Format

The first line contains an integer $k$ ($1 \leq k \leq 10^{18}$), the target speed to reach. It is guaranteed that the given speed can be reached in a finite number of steps.

Output Format

Output one number, the minimum number of spells needed to reach the given speed.

1

0

2

1

10

3

10000

13

Hint

In the first sample, the initial speed is already $1$, so no spells are needed.

In the second sample, you can use the first spell, so the speed increases by $1$ meter per second and becomes exactly $2$ meters per second.

In the third sample, you can use the first spell, then the second spell, then the first spell. The speed changes as follows: $1 \rightarrow 2 \rightarrow 5 \rightarrow 10$. It can be proven that the number of spells needed to reach this speed cannot be smaller.

Translated by ChatGPT 5