• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

Pari and Mari’s favourite recreation is competing against each other in some mathematical games. This time they took a stack of $N$ cards and settled on the following rules:

1. Pari is the first to play, then Mari, then Pari again, then Mari and so on;
2. Pari can take any number of cards (between 1 and $N$, inclusive) from the stack during her first move;
3. In each of the following turns the current player must take at least $1$ card and is allowed to take at most double the amount of cards taken during the previous turn by the other player; naturally, she cannot take more cards than the remaining amount in the stack;
4. The player who takes the last card is the winner.
5. Both Pari and Mari play optimally (i.e. if it is possible for one player to beat the other, that player will always win). Pari can take all the $N$ cards in the first move and win the game, but this makes the game too boring. So she asked you to find the minimum number of cards that she must take during her first turn such that she is guaranteed to win the game.

ورودی

The first and only line of input contains the positive integer $N$, the number of cards in the starting stack.

$$1 \le N \le 10^{15}$$

خروجی

Print the required minimum number of cards that Pari needs to remove during her first turn.

مثال

ورودی نمونه ۱

4

خروجی نمونه ۱

1

ورودی نمونه ۲

8

خروجی نمونه ۲

8