Rathi and Neha are playing an interesting game. There is a stack of N coins in front of them. They take turns in picking up coins from the stack. One may take any number of coins from the stack in one go that is a finite power of 2. The one who picks up the last coin wins! Given the number of coins in the stack, find out who wins the game assuming both play their best game assuming Rathi plays the game first!
Input:
An input contains the only positive integer number N
Output:
Print 1 if Rathi wins and 2 if Neha wins. Also if Rathi wins then print the minimum number of coins he should pick at the first move in order to guarantee his victory.
Constraints:
N ≤ 10^250