Two Nikifors play a funny game. There is a heap of N stones in front of them. Both Nikifors in turns take some stones from the heap. One may take any number of stones with the only condition that this number is a nonnegative integer power of 2 (e.g. 1, 2, 4, 8 etc.). Nikifor who takes the last stone wins.
You are to write a program that determines winner assuming each Nikifor does its best.


An input contains the only positive integer number N (condition N <= 10250 holds).