Description

There are $n$ boxes. At the beginning, each box contains one piece.

Two players take turns. Each move, a player may choose a piece in box $i$ and a positive integer $p$, and move the piece to the box numbered $2^p\times i$. If the box numbered $2^p\times i$ already contains a piece, then both pieces are removed from the box. The player who cannot make a move loses.

Find the $k$-th smallest $n$ such that the second player can win the game.

Input Format

Only one line, containing one positive integer $k$.

Output Format

Only one line, containing one positive integer $n$.

2

10

Hint

For $100\%$ of the testdata, $1\le k<10^9$.

Translated by ChatGPT 5