Fibonacci Game

There are N beads. Two players alternately take beads, and the player who takes the last bead wins.

Player 1 moves first. On the first move, Player 1 may take at least 1 and at most N-1 beads, so taking all beads is not allowed. From then on, a player may take at most twice as many beads as the opponent took on the immediately previous move. For example, if the opponent just took 1 bead, the current player may take 1 or 2 beads.

If N = 3, no matter how Player 1 starts, Player 2 can take all remaining beads. If N = 4, Player 1 can win by taking 1 bead first.

Determine how many beads Player 1 should take on the first move in order to win. If several first moves are winning, output the smallest such number. If every possible first move loses, output -1.

The first line contains an integer N.

• 2 <= N <= 1,000,000

Output the number of beads Player 1 should take on the first move. If no winning first move exists, output -1.