피보나치 게임

구슬 N개가 있다. 두 사람이 번갈아 가며 구슬을 가져가고, 마지막 구슬을 가져간 사람이 이긴다.

첫 번째 플레이어가 먼저 구슬을 가져간다. 첫 차례에는 1개 이상 N-1개 이하의 구슬을 가져갈 수 있으며, 구슬을 모두 가져갈 수는 없다. 그 다음 차례부터는 직전에 상대가 가져간 개수의 두 배 이하로만 가져갈 수 있다. 예를 들어 상대가 직전에 1개를 가져갔다면, 이번 차례에는 1개 또는 2개를 가져갈 수 있다.

N = 3이면 첫 번째 플레이어가 어떻게 시작해도 두 번째 플레이어가 남은 구슬을 모두 가져갈 수 있다. N = 4이면 첫 번째 플레이어가 처음에 1개를 가져가서 이길 수 있다.

첫 번째 플레이어가 이기기 위해 처음에 가져가야 하는 구슬의 개수를 구하라. 가능한 개수가 여러 개라면 가장 작은 값을 출력한다. 어떤 개수를 가져가도 질 수밖에 없다면 -1을 출력한다.

첫째 줄에 정수 N이 주어진다.

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

첫 번째 플레이어가 처음에 가져가야 하는 구슬의 개수를 출력한다. 이길 수 있는 첫 수가 없다면 -1을 출력한다.