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