\includegraphics{https://static.e-olymp.com/content/77/77a8ccd62b7e9eae69ec1bbb74e036c758d3c111.jpg} Дід Мазай та заєць грають у дуже просту гру. Перед ними -- величезна купа з \textbf{n }однакових морквинок. Кожен з них під час свого ходу може взяти з цієї купи довільну кількість морквинок, яка рівна невід'ємній степені числа \textbf{2}, тобто \textbf{1}, \textbf{2}, \textbf{4}, \textbf{8},… . Починає гру або дід Мазай, або заєць. Потім гравці ходять по черзі. Той, хто візьме останню морквинку, той і виграє. Напишіть програму, яка для заданих початкових даних визначає переможця у цій грі. При цьому слід враховувати, що гравці грають оптимально. \InputFile Одне ціле додатне число \textbf{n }(\textbf{n }≤ \textbf{10^\{­­­­250\}}), яке задає кількість морквинок на початку гри. \OutputFile Вивести у першому рядку цифру '\textbf{1}', якщо виграє той, хто ходить першим, або цифру '\textbf{2}' у протилежному випадку. Якщо гру виграв той, хто ходив першим, то у другому рядку повинно міститись мінімальне число морквинок, яке повинен взяти гравець, що виконував хід першим, щоб гарантувати свою перемогу.