Description

There are $n$ stones. Two players play the game with the following rules:

• Mirko takes once first, then Slavko takes once, then Mirko takes once again. They take turns taking stones, and so on.
• On Mirko’s first move, he may take any positive number of stones.
• After that, on each move, the player must take at least one stone and at most $2$ times the number taken in the previous move. Of course, the number taken must not exceed the number of stones currently remaining on the table.
• The player who takes the last stone wins.

Both players play optimally. Mirko wants to know the minimum number of stones he must take on his first move in order to win in the end.

Input Format

One line containing one integer $n$, the number of stones.

Output Format

One line containing one integer, the minimum number of stones Mirko must take to guarantee a win.

4

1

7

2

8

8

Hint

Explanation of Sample 1

For this sample, Mirko can take $1/2/3/4$ stones on his first move. Although taking $4$ stones would win the game immediately, it is not the minimum. The minimum strategy is to take $1$ stone. Then Slavko can only take $1$ or $2$ stones. No matter which one he chooses, Mirko can take all remaining stones on the next move and win.

Constraints

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

Note

Translated from COCI2010-2011 CONTEST #4 T6 HRPA。

Translated by ChatGPT 5