Read an integer variable, and determine the smallest positive integer that has the same number of $\texttt{1}$s in its bit representation as the number you read.

The following numbers all have the same number of $\texttt{1}$s in their bit representation: 7 ($\texttt{111}$), 13 ($\texttt{1101}$), 37 ($\texttt{100101}$), etc. And among all such positive integers, 7 is the smallest number that has 3 $\texttt{1}$s in its bit representation.

Input

The input will contain an integer $A$ ($0 \le A < 1000000$).

Output

Print the smallest positive integer that has the same number of $\texttt{1}$s in its bit representation as $A$.