Binary vs Decimal

Bruce has recently got a job at NEERC (Numeric Expression Engineering Research Center) facility, which studies and produces many kinds of curious numbers. His first assignment is to perform a study of bindecimal numbers.

A positive integer is called bindecimal if its decimal representation is a suffix of its binary representation; both binary and decimal representations are considered without leading zeros. For example, $10_{10}=1010_2$, thus $10$ is a bindecimal number. The numbers $1010_{10}=1111110010_2$ and $42_{10}=101010_2$ are, evidently, not bindecimal.

First of all, Bruce is going to create a list of bindecimal numbers. Help him find the $n$-th smallest bindecimal number.

Input

The first and the only line contains one integer $n(1\le n\le 10^4)$.

Output

Print one integer — the $n$-th smallest bindecimal number in decimal notation.

Examples