Description

A positive number $A$ is considered valid if it contains only 0 or 1, and after converting it to binary as $B$, $A$ is a suffix of $B$.

Now you are given a number $N$. Find the $N$-th such number.

Input Format

One line with one number $N$.

Output Format

One line with one number: the $N$-th number.

2

10

10

1100

Hint

$1 \le N \le 10^4$.

Translated by ChatGPT 5