Задача А
Гра з дробами
Задача 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 , після чого другий гравець програє.