两个最好的朋友 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