eolymp
bolt
Try our new interface for solving problems
Problems

Stones

Stones

Time limit 1 second
Memory limit 128 MiB

There are n stones on the table. Two payers make moves alternatively. For each turn the player can take:

  • 1 or 2 stones, if n is divisible by 3;

  • 1 or 3 stones, if division by 3 gives the residue 1;

  • 1, 2 or 3 stones, if division by 3 gives the residue 2.

Each move can be done only if there is sufficient quantity of stones. The player who can not make a move, lose a game.

Input data

One integer n (0 < n100).

Output data

Print one number 1 or 2 - the number of the winning player in the case of optimal play.

Examples

Input example #1
3
Output example #1
2