Два лучших друга Сережа и Гена играют в игру.
Изначально на столе находится одна кучка из n камней. За один ход нужно взять одну кучку и разбить ее на произвольное число кучек размерами a1 > a2 > ... > ak > 0 камней так, что a1 - a2 = a2 - a3 = ... = ak - 1 - ak = 1. Естественно, количество кучек k должно быть не меньше двух.
Друзья делают ходы по очереди. Проигрывает тот, кто не может сделать ход. Начинает Сережа. Кто выиграет при оптимальной игре обоих?
Выходные данные
Если выигрывает Сережа, выведите k — минимальное число кучек, на которое он может разбить исходную первым ходом при выигрышной стратегии.
Если выигрывает Гена, выведите «-1» (без кавычек).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
|
2
|
|
2
|
6
|
-1
|
|
3
|
100
|
8
|