Barr the Bear and Poe the Penguin like to play games with each other. Today, they took a bag of N pebbles and agreed that they would play by the following rules
If both Poe the Penguin and Barr the Bear played optimally, Poe the Penguin would always get the free lunch. To mock Barr the Bear, Poe the Penguin would like to know the minimum number of stones he must take on his first turn to guarantee a win given optimal play by both sides.
The input contains a single integer N, which denotes the number of stones initially in the bag.
Output the minimum number of stones Poe the Penguin would need to remove on his first turn so that he could still win given optimal play by both sides.
Taken from Chuanqi's 2012 IOI Training Contest 1 with limits reduced.
After removing one stone on his first turn, Poe the Penguin can remove the remaining stones no matter what Barr the Bear plays.
Poe the Penguin removes 2 stones on his first turn. If Barr the Bear removes more than 1 stone on his turn, then Poe the Penguin can remove all remaining stones and win. If Barr the Bear removes a single stone, then Poe the Penguin removes a single stone on his turn again. No matter what Barr the Bear does now, Poe the Penguin is able to remove all remaining stones and win.