Задача А

Гра з дробами

 

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

© LIKT 1998-2018