(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^{5}.

**Output**

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

Public test cases

**Input**

0 1 2 3 4 20 99999 100000

**Output**

2 1 1 1 2 2 1 2

Information

- Author
- Alex Alvarez
- Language
- English
- Translator
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++
- Event
- Vuitè Concurs de Programació de la FME
- Date
- 2011-12-21