Simple game#2816
Grandfather Mazay and the hare play a very simple game. In front of them, there is a huge pile of identical carrots. Each of them, during their turn, can take from this heap any number of carrots equal to a non-negative power of , i.e., , , , , , and so on. Either Grandfather Mazay or the hare begins the game. Then, the players take turns. The one who takes the last carrot wins.
A single positive integer (n \le 10^{250}) — the number of carrots at the beginning of the game.
Print on the first line the digit if the first player wins, or otherwise. If the first player wins, on the second line print the minimal number of carrots that the first player must take in order to guarantee their victory.
Example 1