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
import math
from collections import Counter

n = int(input())
g = [0 for i in range(n + 1)]
prefix_xor = g.copy()


def in_range(d, k):
    if (2 * k - d * d + d) % (2 * d) != 0:
        return -1
    x = (2 * k - d * d + d) / (2 * d)
    return int(x) if x > 0 else -1


def mex(arr):
    counter = Counter()
    for i in arr:
        counter[i] += 1
    for i in range(0, len(arr) + 1):
        if counter[i] == 0:
            return i


def find_move(arr):
    for i in range(0, len(arr)):
        if arr[i] == 0:
            return i
    return -1


for i in range(3, n + 1):
    for_range = range(2, int(math.sqrt(2 * i)) + 1)
    filter_range = [l for l in for_range if in_range(l, i) > 0]
    branches = [prefix_xor[in_range(d, i) + d - 1] ^ prefix_xor[in_range(d, i) - 1] for d in filter_range]
    g[i] = mex(branches)
    prefix_xor[i] ^= g[i]
    if i == n:
        print(-1 if g[i] == 0 else filter_range[find_move(branches)])
