← 返回题目列表

Codeforces · 87/C

C. 有趣的游戏

中文机器翻译题面 查看原题

两个最好的朋友 Serozha 和 Gena 玩游戏。

最初,桌子上有一堆由 n 个石头组成的堆。在一次移动过程中,应取出一堆石子并将其分成任意数量的堆,其中包括 a1 > a2 > ... > ak > 0 颗石子。桩应满足条件a1 - a2 = a2 - a3 = ... = ak - 1 - ak = 1。自然,桩的数量k应不少于2个。

朋友们轮流玩。无法采取行动的玩家就输了。谢罗扎迈出了第一步。如果双方都以最佳方式发挥,谁会获胜?

输入

单行包含一个整数 n (1 ≤ n ≤ 105)。

输出

如果 Serozha 获胜,则打印 k,它代表他在第一步中可以将初始堆分成的最小堆数,以便赢得比赛。

如果 Gena 获胜,则打印“-1”(不带引号)。

示例

输入 #1

3

输出 #1

2

输入 #2

6

输出 #2

-1

输入 #3

100

输出 #3

8