跳跃机器人

题目描述

Y 同学面对一排连续的格子，格子总数为 $N$，编号依次为 $1, 2, \dots, N$。

初始时，Y 同学的一个机器人位于 $1$ 号格子。在每一次跳跃中，若机器人当前位于第 $x$ 号格子，它可以选择跳跃到以下三个位置之一：

1. 第 $x-1$ 号格子；
2. 第 $x+1$ 号格子；
3. 第 $2x$ 号格子。

机器人跳跃时不允许越界，即每一次跳跃的目标位置 $y$ 必须满足 $1 \le y \le N$。

请你帮助 Y 同学计算出，机器人从 $1$ 号格子出发，最少需要跳跃多少次才能到达第 $N$ 号格子。

输入格式

输入仅包含一行一个整数 $N$，表示格子的总数量以及目标格子的编号。

输出格式

输出一行一个整数，表示到达第 $N$ 号格子所需的最少跳跃次数。

样例

样例输入 #1

30

样例输出 #1

6

样例输入 #2

50

样例输出 #2

7

样例输入 #3

64

样例输出 #3

6

样例输入 #4

63

样例输出 #4

8

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 10^6$。