Задача  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, после чего второй игрок проигрывает.