Cross and Cross

Time limit1sMemory limit128 MB

Summary

For a 1×n board where players alternately mark cells and the first to make three consecutive marks wins, decide the winner under optimal play for given n up to 2000.

Level: Hard8 of 10
Topics: Game theory, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Examples4

Example 1
Input
```
3
```
Expected output
```
1
```
Example 2
Input
```
6
```
Expected output
```
2
```
Example 3
Input
```
4
```
Expected output
```
1
```
Example 4
Input
```
5
```
Expected output
```
1
```