미르코와 슬라브코가 좋아하는 취미는 상대와 경쟁하는 수학적인 게임이다. 이번에는 N개의 조약돌이 있는 무더기에 다음과 같은 규칙을 정하였다.

1. 미르코가 선공이며, 그다음 차례는 슬라브코, 그다음 차례는 미르코, 그다음 차례는 슬라브코와 같은 순서이다.
2. 미르코는 처음에 무더기에서 몇개의 조약돌 이건 간에 가져갈수 있다. (모든 조약돌을 다 가져갈 수도 있다.)
3. 그리고 각각의 차례에 플레이어는 적어도 하나에서 이전 차례에 상대가 가져갔던 조약돌 개수의 두 배 까지의 조약돌을 무더기에서 가져올 수 있다. 물론, 무더기에 있는 조약돌의 수 보다 많은 조약돌을 가져올 수는 없다.
4. 마지막 조약돌을 가져온 사람이 승리한다.

입력

출력

입출력 예

입력

4

출력

1

입력

7

출력

2

입력

8

출력

8

출처:coci 2011
번역:august14