Простая игра

Дед Мазай и заяц играют в очень простую игру. Перед ними – огромная куча из N одинаковых морковок. Каждый из них во время своего хода может взять из этой кучи любое количество морковок, равное неотрицательной степени числа 2, т.е. 1, 2, 4, 8,… . Начинает игру либо дед Мазай, либо заяц. Затем игроки ходят по очереди. Тот, кто возьмет последнюю морковку, тот и выигрывает.

Требуется написать программу, которая при заданных исходных данных определяет победителя в этой игре. При этом следует учитывать, что игроки играют оптимально.

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

Входной файл INPUT.TXT содержит единственное целое положительное число N (N ≤ 10²⁵⁰), задающее число морковок в начале игры.

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

Выходной файл OUTPUT.TXT должен содержать в первой строке цифру «1», если выиграет тот, кто ходит первым, или цифру «2» – в противном случае. Если игру выиграл тот, кто ходил первым, то во второй строке этого файла должно содержаться минимальное число морковок, которое должен взять игрок, выполнявший ход первым, чтобы гарантировать свою победу.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]