[COCI2010-2011#4] HRPA

有 $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](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #4](https://hsin.hr/coci/archive/2010_2011/contest4_tasks.pdf) *T6 HRPA***。