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

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

Вхідні дані

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

Результати

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

Приклади

Вхід

2

Результат

1

Вхід

3

Результат

2

Вхід

4

Результат

1

Вхід

5

Результат

2

Вхід

1024

Результат

2

Примітки

Ці приклади частково пояснені також у прикладах до наступної задачі «Палички з ходами, залежними від попереднього — інтерактив».

Оцінювання

• 1-й блок (тести 1-5) містить тести з умови, перевіряється завжди, але безпосередньо не оцінюється.

• 2-й блок (тести 6-10) містить усі значення з діапазону ~6 \leqslant N \leqslant10~ і оцінюється у 30% балів.

• 3-й блок (тести 11-20) має обмеження ~11 \leqslant N \leqslant 100~ й оцінюється у 20% балів.

• 4-й блок (тести 21-30) має обмеження ~101 \leqslant N \leqslant 1234~ й оцінюється у 20% балів.

• 5-й блок (тести 31-40) має обмеження ~12345 \leqslant N \leqslant 43210~ і оцінюється у 15% балів.

• 6-й блок (тести 41-50) має обмеження ~123456 \leqslant N \leqslant 1234567~ і оцінюється у 15% балів.

Для кожного окремо взятого блоку, бали нараховуються, лише якщо успішно пройдено всі тести блоку.