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
def mex(dic):
    if len(dic)==0:
        return 0
    a = set(dic)
    b = min(a)
    if b>0:
        return b-1
    else:
        for i in a:
            if i-b>1:
                return b+1
            else:
                b = i
    return max(a)+1

def sums(x):
    res = []
    for n in range(2,x+1):
        if (2*x-(n-1)*n)%(n*2) != 0:
            continue
        else:
            if x//n - (n-1)//2 < 1:
                break
            res.append((x//n - (n-1)//2, n))
    return res

def f(dic, sost):
    fmex = []
    for a1, n in sums(sost):
        res = 0
        for j in range(n):
            res ^= f(dic, a1 + j) if a1+j not in dic else dic[a1 + j]
        fmex.append(res)
    m = mex(fmex)
    dic[sost] = m
    return m

def find_min(dic, sost):
    for a1, n in reversed(sums(sost)):
        res = 0
        for j in range(n):
            res ^= dic[a1 + j]
        if mex([res])!=0:
            return n



d = dict()
sost1 = int(input())
a = f(d, sost1)
print(find_min(d, sost1) if a else -1)
