eolymp
bolt
Try our new interface for solving problems
Problems

Simple game

Simple game

Time limit 1 second
Memory limit 128 MiB
prb2816

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 data

One positive integer n (n10^250) - the number of carrots at the start of the game.

Output data

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.

Examples

Input example #1
8
Output example #1
1
2
Source 2012-2013 II stage of All Ukrainian school Olympiad, Berdychiv