문제

Author: Goran Žužić

Mirko and Slavko’s favourite pastime is competing against each other in mathematical games. This time they took a heap of N pebbles and settled on the following rules:

1. Mirko is the first to play, then Slavko, then Mirko again, then Slavko and so on; 2. Mirko can take any number of pebbles (between 1 and N, inclusive) from the heap during his first move; 3. In each of the following turns the current player must take at least 1 pebble and is allowed to take at most double the amount of pebbles taken during the previous turn by the other player; naturally, one cannot take more pebbles than the remaining amount in the heap; 4. The player who takes the last pebble is the winner.

Both Mirko and Slavko play optimally (if it is possible for one player to beat the other, that player will always win). We need to find the minimum number of pebbles that Mirko must take during his first turn such that he is guaranteed to win the game.

입력

The first and only line of input contains the positive integer N (2 ≤ N ≤ 1015), the number of pebbles in the starting heap.

출력

The first and only line of output must contain the required minimum number of pebbles that Mirko needs to remove during his first turn.

예제 입력 1

4

예제 출력 1

1

예제 입력 2

7

예제 출력 2

2

예제 입력 3

8

예제 출력 3

8