A8074 | Interesting Game

Two best friends Serozha and Gena play a game.

Initially there is one pile consisting of $n$ stones on the table. During one move one pile should be taken and divided into an arbitrary number of piles consisting of $a_{1}>a_{2}>...>a_{k}>0$ stones. The piles should meet the condition $a_{1}-a_{2}=a_{2}-a_{3}=...=a_{k-1}-a_{k}=1$ . Naturally, the number of piles $k$ should be no less than two.

The friends play in turns. The player who cannot make a move loses. Serozha makes the first move. Who will win if both players play in the optimal way?

The single line contains a single integer $n$ ( $1<=n<=10^{5}$ ).

If Serozha wins, print $k$ , which represents the minimal number of piles into which he can split the initial one during the first move in order to win the game.

If Gena wins, print "-1" (without the quotes).