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