当前没有测试数据。

描述

地上有一排格子，共 $n$ 个位置。机器猫站在第一个格子上，需要取第 $n$ 个格子里的东西。

机器猫当然不愿意自己跑过去，所以机器猫从口袋里掏出了一个机器人！这个机器人的行动遵循下面的规则：

初始时，机器人位于 $1$ 号格子 若机器人目前在 $x$ 格子，那么它可以跳跃到 $x−1,x+1,2x$ 里的一个格子（不允许跳出界） 问机器人最少需要多少次跳跃，才能到达 $n$ 号格子。

输入描述

仅一行，一个正整数，表示 $n$。

输出描述

仅一行，一个正整数，表示最少跳跃次数。

30

6

提示

第一组样例： $1→2→4→8→16→15→30$

数据规模与约定

对于 $100$ 的数据，有 $1≤n≤1000000$。