Є одна купка, яка спочатку містить ~N~ паличок. Двоє грають у таку гру. Кожен з гравців на кожному своєму ході може забрати з купки або 1, або 2, або 3 палички (але, звісно, не більше, чим їх є в купці). Ніяких інших варіантів ходу нема. Ходять гравці по черзі, пропускати хід не можна. Виграє той, хто забирає останню паличку (можливо, разом із ще однією або ще двома).

Напишіть програму, яка визначатиме, хто виграє при правильній грі обох гравців. Іншими словами, хто може забезпечити собі виграш, хоч би як не грав інший.

Вхідні дані

Єдине ціле число ~N~ (~1\leqslant N\leqslant 12345~) — початкова кількість паличок у купці.

Результати

Єдине ціле число, або 1 (якщо перший гравець може забезпечити собі виграш), або 2 (якщо другий).

Приклади

Вхід

2

Результат

1

Вхід

25

Результат

1

Вхід

256

Результат

2