Math Game

Time limit1sMemory limit128 MB

Summary

Given N coins in a Fibonacci-like alternating take game, find the minimum first move Sangdeok can make to guarantee a win under optimal play.

Level: Medium6 of 10
Topics: Game theory, Math, Greedy
Solved: No attempts yet

Problem

Sangdeok and Heewon play a game with N coins. Starting with Sangdeok, they alternate turns and take coins from the pile.

On the first turn, Sangdeok may take any number of coins from 1 through N. On every later turn, the player may take at most twice as many coins as were taken on the immediately previous turn, and must take at least 1 coin.

The player who takes the last coin wins. Assuming both players play optimally, find the minimum number of coins Sangdeok must take on the first turn to guarantee a win.

Input

The first line contains the number of coins N. (2 <= N <= 10^15)

Output

Print the minimum number of coins Sangdeok must take on the first turn to guarantee a win.

Hint

When N is 4, Sangdeok may take 1, 2, 3, or 4 coins on the first turn. Taking all 4 coins wins immediately, but it is not the minimum. If Sangdeok takes 1 coin, 3 coins remain and Heewon may take at most 2 coins on the next turn. Whether Heewon takes 1 or 2 coins, Sangdeok can take all remaining coins on his next turn, so the minimum is 1.

Examples3

Example 1
Input
```
4
```
Expected output
```
1
```
Example 2
Input
```
7
```
Expected output
```
2
```
Example 3
Input
```
8
```
Expected output
```
8
```