题目描述

哥萨克胡子的朋友们收到了那封秘密信件。原来，里面有一张古代魔法鞋的设计图。这种魔法鞋能让穿上它的人加速到惊人的速度。穿着这双鞋的人初始速度为每秒 $1$ 米。

如果穿着魔法鞋的人当前速度为每秒 $a$ 米，那么她可以施展以下两种咒语之一：

• 将自身速度增加 $a$ 米每秒。
• 将自身速度增加 $a+1$ 米每秒。

穿着魔法鞋的人需要至少念动多少次咒语，才能将速度精确提升到每秒 $k$ 米？

输入格式

第一行包含一个整数 $k$ ($1 \leq k \leq 10^{18}$) —— 需要达到的目标速度。保证可以在有限步数内加速到给定的速度。

输出格式

输出一个数字 —— 为达到给定速度所需的最少咒语念动次数。

1

0

2

1

10

3

10000

13

提示

第一个样例中，初始速度已经等于 $1$，因此可以不使用咒语。

第二个样例中，可以使用第一种咒语，这样速度将增加 $1$ 米每秒，正好变为 $2$ 米每秒。

第三个样例中，可以连续使用第一种、第二种、第一种咒语。速度将按如下方式变化：$1 \rightarrow 2 \rightarrow 5 \rightarrow 10$。可以证明，达到此速度所需的咒语次数不能更少。