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

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

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

Одно целое положительное число n (n ≤ 10250), задающее число морковок в начале игры.

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

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