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*<sub class="lower-index">1</sub> &gt; *a*<sub class="lower-index">2</sub> &gt; ... &gt; *a*<sub class="lower-index">*k*</sub> &gt; 0 stones. The piles should meet the condition *a*<sub class="lower-index">1</sub> - *a*<sub class="lower-index">2</sub> = *a*<sub class="lower-index">2</sub> - *a*<sub class="lower-index">3</sub> = ... = *a*<sub class="lower-index">*k* - 1</sub> - *a*<sub class="lower-index">*k*</sub> = 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<sup class="upper-index">5</sup>).
none
import sys
from array import array  # noqa: F401


def input():
    return sys.stdin.buffer.readline().decode('utf-8')


n = int(input())
dp = [0] * (n + 1)

for i in range(2, n):
    nim = dp[i] ^ 1
    total = i

    for j in range(i - 1, 0, -1):
        total += j
        nim ^= dp[j]
        if total > n:
            break
        dp[total] |= nim

        if total == n:
            print(i - j + 1)
            exit()

print(-1)
