(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++