HCT00001 - Interesting Game with Polygons

Rijél is a very wise teacher. He loves mathematics, especially games and geometry problems. Recently one of his students challenged him to the following game:

Initially, there is a polygon with N vertices drawn in the plane. The polygon is strictly convex, i.e., each internal angle is strictly smaller than 180 degrees. The vertices of the polygon are numbered 1 through N, in clockwise order.

Two players play the game on this polygon. The players take alternating turns. In each turn, the current player chooses a diagonal or a side of the polygon and draws it as a straight line segment. (A diagonal of the polygon is a line segment that connects any two non-adjacent vertices of the polygon.) The player is only allowed to choose a diagonal or a side that does not intersect any of the previously drawn segments (it must not share endpoints with any of them either). The player who cannot draw a diagonal or a side according to the above rules loses the game.

You are given the int N.

We assume that both players play the game optimally. Return 1 if the first player wins and 2 otherwise.

Input

The only line of input contains N (3 ≤ N ≤ 1000), the number of vertices of the polygon.

Output

Print 1 if the first player wins, or 2 otherwise.

Example

Input
3
4
15

Output
1
1
2

Added by:kojak_
Date:2014-10-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2015-07-26 17:17:30 Xuzheng J
I tested it and found N>=3 for all tests
2015-07-26 16:41:49 Xuzheng J
What is N=1 and N=2?
It is not a strictly convex in the plane
2014-10-27 00:34:44 Jaime Rojas
Can anyone provide more Test Cases?
2014-10-20 17:12:35 RIVU DAS
Can you check whether my I/O format is correct or not?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.