수학 게임

상덕이와 희원이는 N개의 동전으로 게임을 한다. 두 사람은 상덕이부터 시작해 번갈아 한 번씩 동전을 가져간다.

첫 번째 턴에서 상덕이는 1개 이상 N개 이하의 동전을 가져갈 수 있다. 그 이후의 각 턴에서는 바로 직전 턴에 가져간 동전 수의 2배 이하만큼 동전을 가져갈 수 있으며, 적어도 1개는 가져가야 한다.

마지막 동전을 가져가는 사람이 이긴다. 두 사람이 모두 최적으로 플레이할 때, 상덕이가 반드시 이기기 위해 첫 번째 턴에서 가져가야 하는 동전 수의 최솟값을 구하라.

첫째 줄에 동전의 개수 N이 주어진다. (2 <= N <= 10^15)

상덕이가 반드시 이기기 위해 첫 번째 턴에서 가져가야 하는 동전 수의 최솟값을 출력한다.

N이 4일 때 상덕이가 첫 번째 턴에서 가져갈 수 있는 동전 수는 1, 2, 3, 4개이다. 4개를 가져가면 바로 이기지만 최솟값은 아니다. 상덕이가 1개를 가져가면 3개가 남고, 희원이는 다음 턴에서 최대 2개까지만 가져갈 수 있다. 희원이가 1개 또는 2개를 가져가더라도 상덕이는 자신의 다음 턴에서 남은 동전을 모두 가져갈 수 있으므로, 최솟값은 1이다.