На столе лежат n камней. Играют двое, ходят по очереди. За ход игрок может взять:

• 1 или 2 камня, если n делится на 3;
• 1 или 3 камня, если дает остаток 1;
• 1, 2 или 3 камня, если дает остаток 2.

Каждый ход можно сделать только при наличии достаточного количества камней. Проигрывает тот, кто хода сделать не может.

Входные данные

Одно целое число n (0 < n ≤ 100).

Выходные данные

Выведите одно число 1 или 2 - номер игрока, который выигрывает при правильной игре.