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