Battle Bots. CC BY-SA 2.0，作者为 Flickr 上的 Jeremy Blum

你正在参加机器人大战激斗大赛（Battle-bots Aggressive Power Contest）。这是一个每个队伍建造一个机器人与其他机器人战斗的比赛，你通过摧毁对手的机器人来获胜。具体来说，当对手机器人的唯一电机被摧毁并停止移动时，你就获胜了。

你为你的机器人装备了两种武器：一把可以将对手机器人劈成两半的剑，以及一个可以从对手机器人身上撕下一块并将其压碎成废铁的爪子。这两种攻击所花费的时间相同。控制你机器人的程序一直在运行，以决定下一步使用哪种攻击。

如果你的机器人使用剑攻击将对手劈成两半，带有电机的这一半将继续移动，你可以忽略另一半。如果你的机器人使用爪子攻击，它将从对手机器人身上撕下大小为 $1$ 的一块，但除非你能彻底消灭该机器人，否则你必须假设机器人的电机位于你没有用爪子攻击的那部分中，并继续战斗。

例如，考虑第二个样例。如果你的对手机器人大到需要 $5$ 次爪击才能完全粉碎它，你可以按如下方式行动。首先用剑劈砍，将其切成两个大小为 $2\frac{1}{2}$ 的部分。然后对仍在移动的部分使用爪子，使其大小降至 $1\frac{1}{2}$。再次用剑将该部分劈成两半，使其大小降至 $\frac{3}{4}$。最后使用爪子粉碎机器人最后移动的部分。这样，你就可以在四次攻击中击败它。

你的机器人配备了一台量子计算机，每微秒可以轻松模拟一古戈尔（googol）种攻击模式。然而，如果它不知道最快的攻击模式是什么，它就永远不会知道自己已经找到了它，并且永远不会停止搜索。

编写一个程序来完善你的机器人：给定消灭对手所需的爪击次数，确定在最坏情况下消灭对手所需的最少攻击次数。

输入格式

输入包含：

• 一行，包含一个整数 $n$ ($1 \le n \le 10^{18}$)，表示消灭对手机器人所需的爪击次数。

输出格式

输出摧毁对手机器人所需的最少攻击次数。

样例

输入样例 1

5

输出样例 1

4

输入样例 2

6

输出样例 2

4

输入样例 3

3

输出样例 3

3