Задача  SG2016.  Двоє грають у наступну гру. На дошці записують дроби 1/n, 2/n, ..., n-1/n. За один хід гравець може вибрати деяку непорожню послідовність дробів (можливо, лише один) та скоротити чисельник і знаменних кожного з них на ціле число, більше 1 (для кожного з дробів це число вибирається окремо). Той, хто не може зробити хід, програє. Виведіть номер переможця при умові, що обидва гравці грають оптимально.

Технічні умови Програма зчитує з пристрою стандартного введення єдине ціле число n (2 ≤ n ≤10⁶). Програма виводить на пристрій стандартного виведення єдине ціле число - номер переможця за умови оптимальної гри обох гравців.

 Приклади

Введення 3

Виведення 2

Введення 4

 Виведення 1

Коментар. У першому тесті на дошці записано числа 1/3 та 2/3.  Перший гравець не може зробити хід і тому програє. У другому тесті на дошці записано 1/4, 2/4, 3 /4. Єдиний можливий хід - скоротити дріб 2/4 на 2 , після чого другий гравець програє.