Problem Description

There are $n$ stones. Two players have established the following rules for the game:

• Mirko takes first, followed by Slavko, then Mirko again, and they alternate in taking stones;
• Mirko can take any number of stones on his first turn;
• Subsequently, each player must take at least one stone and at most twice the number of stones taken by the previous player. Of course, the number of stones taken must not exceed the number of stones remaining on the field;
• The player who takes the last stone wins.

Both players use optimal strategies. Mirko wants to know the minimum number of stones he needs to take on his first turn to ensure his victory.

Input Format

A single line containing an integer $n$, representing the number of stones.

Output Format

A single line containing an integer, representing the minimum number of stones Mirko needs to take to guarantee his victory.

Sample Input and Output

Sample Input #1

4

Sample Output #1

1

Sample Input #2

7

Sample Output #2

2

Sample Input #3

8

Sample Output #3

8

Notes

Sample 1 Explanation

For this example, Mirko can take $1/2/3/4$ stones on his first turn. Although taking $4$ stones would win the game immediately, it is not the minimum. The minimum strategy is to take $1$ stone. This way, Slavko can only take $1$ or $2$ stones. Regardless of his choice, Mirko can take all remaining stones in the next turn and win.

Data Range and Constraints

For $100\%$ of the data, it is guaranteed that $2\le n\le 10^{15}$.

Notes

This problem is translated from COCI2010-2011 CONTEST #4 T6 HRPA.

见题面 Input 部分

见题面 Output 部分