Language:

English
Russian

Практикум по программированию

Для участников:
Регистрация  ||   Вход
Список соревнований
Вы не вошли в систему! Вход или регистрация.

Вычитание квадратов

Time limit:5 sec.
Memory limit: 262144 KByte

Двое играют в следующую игру. Сначала на доске записано целое число N. Ход состоит в том, чтобы вычесть из текущего числа квадрат положительного целого числа так, чтобы разность была неотрицательна. Проигрывает тот, у кого нет хода. Кто выиграет при правильной игре?

Входные данные

В единственной строке ввода дано натуральное число 1 ≤ N ≤ 3 × 107

Выходные данные

В единственной строке выведите 1, если выигрывает начинающий игрок, и 2 – если второй игрок.

Примеры

Входные данные
5
Выходные данные
2
Входные данные
8
Выходные данные
1

Примечание

Набор тестов дополнен по сравнению с тем, что использовался на олимпиаде

© Copyright ВоГУ, АВТ, Носов Д.А., Смоленцев К.Н.