题目描述

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

• A , B 轮流取石子，以此类推；
• A 在第一次取石子时可以取走任意多个；
• 接下来，每次至少要取走一个石子，最多取走上一次取的数量的 $2$ 倍。且取走的数量必须不大于剩余的石子数量。
• 先清空石子的玩家获胜。

设双方都以最优策略取石子。求 A 第一次至少要取走几颗石子最终才能够获胜。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

4

样例输出 #1

1

样例 #2

样例输入 #2

7

样例输出 #2

2

样例 #3

样例输入 #3

8

样例输出 #3

8

提示

样例 1 解释

A 第一次可以取 $1/2/3/4$ 个。最少的方案是取走 $1$ 个。这样 B 只能取走 $1$ 个或者 $2$ 个。无论选择哪种，A 下一步都能获胜。

数据规模与约定

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