Mirko 和 Slavko 最喜欢的消遣活动是在数学游戏中互相竞争。这一次，他们拿了一堆含有 $N$ 个石子的石子堆，并约定了以下规则：

1. Mirko 先手，然后是 Slavko，接着又是 Mirko，然后是 Slavko，依此类推；
2. Mirko 在他的第一步中可以从石子堆中取走任意数量的石子（在 $1$ 到 $N$ 之间，包含两端）；
3. 在接下来的每个回合中，当前玩家必须至少取走 $1$ 个石子，且最多只能取走对手在上一个回合中所取石子数量的两倍；当然，取走的石子数不能超过石子堆中剩余的石子数；
4. 取走最后一个石子的玩家获胜。

Mirko 和 Slavko 都采取最优策略（如果其中一个玩家有必胜策略，该玩家就一定会赢）。我们需要求出 Mirko 在他的第一步中必须取走的最少石子数量，以确保他能够赢得游戏。

输入格式

输入的第一行，也是唯一的一行，包含一个正整数 $N$ ($2 \le N \le 10^{15}$)，表示初始石子堆中的石子数量。

输出格式

输出的第一行，也是唯一的一行，必须包含 Mirko 在他的第一步中需要取走的最少石子数量。

样例

输入样例 1

4

输出样例 1

1

输入样例 2

7

输出样例 2

2

输入样例 3

8

输出样例 3

8

说明

样例 1 说明

Mirko 有 4 种选择：他可以从石子堆中取走 1、2、3 或 4 个石子。如果他取走全部 4 个石子，他自然会赢，但这并不是最少石子的解。我们需要检查其他备选项。如果 Mirko 只取走 1 个石子，留给 Slavko 的是 3 个石子的石子堆，但 Slavko 最多只能取走 2 个。Slavko 无法取走所有的石子，而 Mirko 将能够在他的下一个回合中取走所有剩余的石子，从而赢得游戏。因此，我们得出结论，对于这个测试用例，1 是最少石子的解。