크로스와 크로스

크로스와 크로스는 1 × n 크기의 보드에서 진행하는 게임이다. 보드는 1 × 1 크기의 칸 n개가 한 줄로 늘어서 있으며, 두 플레이어가 번갈아 가며 자신의 차례를 진행한다.

각 플레이어는 자신의 차례에 아직 비어 있는 칸 하나를 골라 그 칸에 '×' 표시를 한다.

어떤 플레이어가 표시를 놓은 결과 가로로 연속한 3개의 칸이 모두 '×'가 되면, 그 표시를 놓은 플레이어가 즉시 승리한다.

n이 주어질 때, 두 플레이어가 모두 최적으로 플레이한다고 가정하고 누가 이기는지 구하는 프로그램을 작성하시오. 먼저 두는 플레이어를 첫 번째 플레이어라고 부른다.

첫째 줄에 정수 n이 주어진다. (3 ≤ n ≤ 2000)

첫 번째 플레이어(먼저 두는 플레이어)가 이기면 1을, 두 번째 플레이어가 이기면 2를 출력한다.