Polygon Game

Time limit2sMemory limit512 MB

Summary

Two players alternately draw chords inside a convex N-gon that avoid all earlier chords, including shared endpoints; decide the winner under optimal play.

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

Problem

A convex polygon has $N$ vertices. Every interior angle is smaller than $180^\circ$ , and the vertices are numbered $1$ through $N$ in clockwise order.

Seonggwan and Hongjun play a game on this polygon. Seonggwan moves first, and the two players alternate turns.

On a turn the player picks two vertices and draws the segment that joins them. The segment is allowed to lie on a side of the polygon. The new segment must not meet any segment drawn earlier. Two segments that touch at an endpoint count as meeting.

The player who cannot draw a segment loses. Given $N$ , write a program that decides who wins when both players play optimally.

Input

The first line contains $N$ ( $3 \le N \le 1000$ ).

Output

Print $1$ if Seonggwan wins, or $2$ if Hongjun wins.

Examples4

Example 1
Input
```
3
```
Expected output
```
1
```
Example 2
Input
```
4
```
Expected output
```
1
```
Example 3
Input
```
15
```
Expected output
```
2
```
Example 4
Input
```
191
```
Expected output
```
2
```