Том і Джеррі, нудьгуючи в цій пандемії, вирішують пограти в гру.

Дано ціле число \(N\). Під час кожного ходу гравця цей гравець робить хід, віднімаючи дільник поточного \(N\) (який менший за N) від \(N\), таким чином утворюючи нове \(N\) для наступного ходу.

Гравець, у якого не залишилося дільника для віднімання, програє гру. Гра починається з того, що Том робить перший хід. І Том, і Джеррі грають оптимально. Завдання полягає в тому, щоб визначити, хто переможе в грі. Виведіть 1, якщо виграє Том, інакше - 0.

Формат вхідних даних

Вхідний потік містить ціле число \(N\)

Формат вихідних даних

У вихідний потік вивести відповідь.

Обмеження

\(1 ≤ N ≤ 10^8\)

Приклад вхідних даних

2

Приклад вихідних даних

1

Приклад вхідних даних

1

Приклад вихідних даних

0