결함 게임

택희와 현우는 보드판 하나와 크기가 서로 다른 $N$개의 돌을 이용해 게임을 한다. 게임의 규칙은 다음과 같다.

• '돌탑'은 크기가 가장 큰 돌이 아래, 가장 작은 돌이 위에 오도록 크기 순으로 정렬되어 쌓인 돌무더기를 뜻한다.
• 처음에는 크기가 $1, 2, \ldots, N$인 돌이 하나씩 있고, 보드판은 비어 있다. 두 플레이어는 번갈아가며 보드판에 새로운 돌탑의 바닥을 만들거나, 보드판 위에 있는 기존 돌탑 위에 돌 하나를 올려놓는다. 각 크기의 돌은 하나씩만 있으며 두 플레이어가 공유한다. 한번 보드판 위에 올라간 돌은 이후 아무도 손댈 수 없다.
• 각 플레이어는 턴마다, 보드 위 돌탑 중 어딘가에 올릴 수 있는 돌이 남아 있다면, 반드시 그러한 돌 중 하나를 골라 올릴 수 있는 돌탑 중 원하는 돌탑 위에 올려야 한다.
• 어떤 돌탑에도 돌을 올릴 수 없다면, 남은 돌 중 아무거나 하나를 골라 보드 위에 새로운 돌탑의 바닥을 만든다.
• 모든 돌이 소진된 뒤, 돌탑의 개수가 홀수이면 선공이 이기고, 짝수이면 후공이 이긴다.

택희와 현우는 항상 최선을 다하며, 이길 수 있는 상황에서는 반드시 이긴다고 가정한다. 이 게임의 승자는 누구일까?

첫째 줄에 돌의 개수 $N$이 주어진다. ($1 \le N \le 5,000,000$)

선공이 이긴다면 1을, 후공이 이긴다면 2를 출력한다.