Defect Game

Time limit0.5sMemory limit512 MB

Summary

Given N stones of sizes 1 to N, two players alternately build stone towers under forced-move rules, and the answer is the winner decided by the parity of the final tower count.

Level: Medium7 of 10
Topics: Game theory, Math
Solved: No attempts yet

Problem

Taehee and Hyunwoo are playing a game with a board and $N$ stones of different sizes. The rules are as follows.

A 'stone tower' is a pile of stones stacked in size order, with the largest stone at the bottom and the smallest at the top.
At the start, there is one stone of each size $1, 2, \ldots, N$ and an empty board. The two players take turns. On a turn, a player either starts a new stone tower on the board or places one stone on an existing stone tower on the board. Each size of stone exists only once, and the two players share all the stones. Once a stone is placed on the board, no one may touch it again.
On each turn, if some stone still left can be placed on a stone tower on the board, the player must choose one such stone and place it on any stone tower where it can go.
If no stone can be placed on any stone tower, the player chooses any one of the remaining stones and starts a new stone tower on the board with it.
After all stones are used, the first player wins if the number of stone towers is odd, and the second player wins if it is even.

Taehee and Hyunwoo always play their best, and each wins whenever a win is possible. Who wins this game?

Input

The first line contains the number of stones $N$ . ( $1 \le N \le 5,000,000$ )

Output

If the first player wins, print 1. If the second player wins, print 2.

Examples2

Example 1
Input
```
2
```
Expected output
```
1
```
Example 2
Input
```
6
```
Expected output
```
1
```