Division Game

Time limit1sMemory limit512 MB

Summary

Starting from a pile of N stones, players split a pile into k consecutive descending piles; find the smallest winning first split or -1.

Level: Medium7 of 10
Topics: Game theory, Dynamic programming, Math, Implementation
Solved: No attempts yet

Problem

Gusagwa and Cubelover are going to play a division game. The game starts with a single pile containing N stones. The two players take turns, and Gusagwa takes the first turn. On each turn, the following can be done.

Choose one pile of stones and divide it into k piles (k ≥ 2).
If the numbers of stones in the newly created piles are a1, a2, ..., ak, then a1 > a2 > ... > ak > 0 and a1 - a2 = a2 - a3 = ... = ak-1 - ak = 1 must hold.

The player who has no pile left to divide loses the game. Write a program that determines who wins when both players play optimally.

Input

The first line gives N (1 ≤ N ≤ 100,000).

Output

If Gusagwa wins, print the number k of piles that Gusagwa creates on the first turn. If several values of k are possible, print the smallest one. If Cubelover wins, print -1.

Examples3

Example 1
Input
```
3
```
Expected output
```
2
```
Example 2
Input
```
6
```
Expected output
```
-1
```
Example 3
Input
```
100
```
Expected output
```
8
```