Bituś and Bajtuś are playing "binary dodgeball." The game is played on a board consisting of $n$ squares numbered from 1 to $n$. There is one pawn on each square. Players take turns. A move consists of taking a pawn from square $i$ and moving it to square $2^{k}i$, for any $k \ge 1$, provided that such a square exists. If there was a pawn on the new square, a "capture" occurs, and both pawns are eliminated from the game. The player who cannot make a move loses.

Each time, Bituś prepares the board (i.e., chooses a positive integer $n$) and magnanimously gives the first move to Bajtuś. However, Bituś does not like to lose, so he decided to always choose a board on which the second player has a winning strategy. This is the case, for example, for boards of lengths 1, 10, or 11. He does not want Bajtuś to start suspecting anything, so he must choose a board of a different size each time.

He has asked you for help. Write a program that, for a given number $k$, outputs the $k$-th smallest board size for which the second player has a winning strategy.

Input

The only line of input contains a single integer $k$ ($1 \le k \le 1\,000\,000\,000$).

Output

The only line of output should contain a single integer equal to the size of the $k$-th smallest board that guarantees a win for the second player.

Examples

Input 1

2

Output 1

10