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?

Input

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

Output

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).