Cross and Cross

Cross and Cross is a game played on a board of size 1 × n. The board is a single row of n unit cells (each 1 × 1), and two players alternate taking turns.

On your turn, you choose one empty cell and place an '×' mark in it.

If, as a result of a player's move, three horizontally consecutive cells all contain '×', that player wins immediately.

Given n, and assuming both players play optimally, determine which player wins. The player who moves first is called the first player.

The first line contains an integer n. (3 ≤ n ≤ 2000)

Print 1 if the first player (the one who moves first) wins, or 2 if the second player wins.