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