题目描述

有 $n$ 枚石子。两位玩家定了如下规则进行游戏：

• Mirko 先取一次，Slavko 再取一次，然后 Mirko 再取一次，两人轮流取石子，以此类推；
• Mirko 在第一次取石子时可以取走任意多个；
• 接下来，每次至少要取走一个石子，最多取走上一次取的数量的 $2$ 倍。当然，玩家取走的数量必须不大于目前场上剩余的石子数量。
• 取走最后一块石子的玩家获胜。

双方都以最优策略取石子。Mirko 想知道，自己第一次至少要取走几颗石子最终才能够获胜。

输入格式

输入一行一个整数 $n$，表示石子的数量。

输出格式

输出一行一个整数，表示 Mirko 最少取多少石子可以保证获胜。

4

1

7

2

8

8

提示

样例 1 解释

对于这个样例，Mirko 第一次可以取 $1/2/3/4$ 个。虽然他取 $4$ 个会直接赢得比赛，但这并不是最少的。最少的方案是取走 $1$ 个。这样 Slavko 只能取走 $1$ 个或者 $2$ 个。无论选择哪种，Mirko 下一步都能取走所有的石子并获胜。

数据规模与约定

对于 $100\%$ 的数据，保证 $2\le n\le 10^{15}$。

说明

题目译自 COCI2010-2011 CONTEST #4 T6 HRPA。