Grandfather Mazay and the hare play a very simple game. In front of them there is a huge pile of n identical carrots. Each of them during his turn can take from this heap any number of carrots equal to the non-negative degree of 2, i.e. 1, 2, 4, 8, ... . Either Grandfather Mazay or the hare begins the game. Then the players take turns. The one who takes the last carrot wins.

Write a program that by the initial data determines the winner in this game. It is known that players play optimally.

Input

One positive integer n (n ≤ 10250) - the number of carrots at the start of the game.

Output

Print in the first line the number 1, if the one who goes first wins, or the number 2 otherwise. If the game was won by the one who made turn first, then the second line should contain the minimum number of carrots that must be taken by the player who made the first move to guarantee his victory.