Math Game

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.

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

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

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.