Problem Description

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

1. Poe the Penguin would move first since Barr the Bear was lazy.
2. Poe the Penguin can take any number of stones (from 1 to N) from the bag of stones during this first move.
3. In each of the following moves the current player must take at least 1 stone from the bag, and he can take up to double the number of stones taken during the previous turn. Obviously, he cannot take more stones than there are in the bag.
4. The player who takes the last stone is the winner, and gets treated to a free lunch.

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.

Input

The input contains a single integer N, which denotes the number of stones initially in the bag.

Output

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.

Subtask 1 (20 points)

Subtask 2 (30 points)

Subtask 3 (50 points)

Acknowledgements

Taken from Chuanqi's 2012 IOI Training Contest 1 with limits reduced.

Sample Input 1

4

Sample Output 1

1

Explanation for Sample Output 1

After removing one stone on his first turn, Poe the Penguin can remove the remaining stones no matter what Barr the Bear plays.

Sample Input 2

7

Sample Output 2

2

Explanation for Sample Output 1

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.