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
3
2
6
-1
100
8
33
2
23
-1
35
-1
15
2
99
2
46
4
78
4
627
2
250
5
873
18
871
-1
684
-1
303
2
93764
-1
39509
-1
70878
-1
7578
3
31893
3
57113
2
66873
2
9564
3
42237
18
92763
22
38798
76
63359
34
573
3
60879
2
67341
2
15748
8
42602
17
67817
73
81207
6
8149
2
95298
4
41385
15
27443
2
74424
21
35708
-1
36655
-1
34378
-1
63478
-1
42863
-1
19715
-1
37317
-1
96992
-1
56056
-1
45899
-1
1
-1
100000
-1
56
-1
38
-1
1515
2
# LUOGU_RID: 132710750
from functools import reduce

n = int(input())
sg = [0 for _ in range(n + 1)]
xorSum = [0 for _ in range(n + 1)]
L = [[] for _ in range(n + 1)]
len = 2

while True:
    if len * (len + 1) // 2 > n:
        break
    a1 = 1
    while True:
        sum = (2 * a1 + len - 1) * len // 2
        if sum > n:
            break
        L[sum].append((a1, a1 + len - 1))
        a1 += 1
    len += 1

for i in range(3, n + 1):
    S = set()
    for p in L[i]:
        S.add(xorSum[p[1]] ^ xorSum[p[0] - 1])
    while sg[i] in S:
        sg[i] += 1
    xorSum[i] = xorSum[i - 1] ^ sg[i]

print(-1 if sg[n] == 0 else reduce(lambda x, y: min(x, y), map(lambda x: x[1] - x[0] + 1 if (xorSum[x[1]] ^ xorSum[x[0] - 1]) == 0 else n, L[n])))
