Дед Мазай и заяц играют в очень простую игру. Перед ними – огромная куча из n одинаковых морковок. Каждый из них во время своего хода может взять из этой кучи любое количество морковок, равное неотрицательной степени числа 2, т.е. 1, 2, 4, 8,… . Начинает игру либо дед Мазай, либо заяц. Затем игроки ходят по очереди. Тот, кто возьмет последнюю морковку, тот и выигрывает.
Напишите программу, которая при заданных исходных данных определяет победителя в этой игре. При этом следует учитывать, что игроки играют оптимально.
Одно целое положительное число n (n ≤ 10^{250}), задающее число морковок в начале игры.
Вывести в первой строке цифру '1', если выиграет тот, кто ходит первым, или цифру '2' - в противном случае. Если игру выиграл тот, кто ходил первым, то во второй строке должно содержаться минимальное число морковок, которое должен взять игрок, выполнявший ход первым, чтобы гарантировать свою победу.