The burger's game P28661

(The original statement in Catalan has some private jokes. This English version goes straight to the point of the problem.)

Consider the following two-player game. There is a plate with n burgers. By turns, each player eats a number of Fibonacci of burgers (at least one). The first player that cannot eat, loses. Please write a program to tell who wins, assuming perfect play.

Input

Input consists of several cases, each with a natural number between 0 and 10⁵.

Output

For every case, print the number of the winning player (1 or 2), assuming perfect play by both players.