Проста гра#2816
Дідусь Мазай і заєць грають дуже просту гру. Перед ними лежить велика купа з однакових морквин. Кожен з них під час свого ходу може взяти з цієї купи будь-яку кількість морквин, яка дорівнює невід'ємному степеню , тобто , , , , і так далі. Гру починає або дідусь Мазай, або заєць. Далі гравці ходять по черзі. Перемагає той, хто забирає останню морквину.
Дано одне додатне ціле число (n \le 10^{250}) — кількість морквин на початку гри.
Виведіть у першому рядку цифру , якщо перемагає перший гравець, або інакше. Якщо перемагає перший гравець, то у другому рядку виведіть мінімальну кількість морквин, яку він має взяти, щоб забезпечити собі перемогу.
Приклад 1