Base-2 Palindromes

Interview

Time limit1sMemory limit256 MB

Summary

Find the M-th positive integer whose binary representation reads the same forward and backward and print it in decimal.

Level: Medium5 of 10
Topics: Bit manipulation, Math
Solved: No attempts yet

Problem

A positive integer $N$ is a base- $b$ palindrome when the base- $b$ representation of $N$ reads the same forward and backward. For example, the decimal number 7 is a single digit in every base 8 or larger, so it is a palindrome in all of those bases. It is a palindrome in base 2 ( $111$ ) and in base 6 ( $11$ ) as well, but not in base 3 ( $21$ ), base 4 ( $13$ ), base 5 ( $12$ ), or base 7 ( $10$ ). Written in base 10 and sorted from smallest, the base-2 palindromes begin 1, 3, 5, 7.

Find the $M$ -th base-2 palindrome and print it in base 10.

Input

The first line contains one positive integer $M$ written in base 10. ( $1 \le M \le 50000$ )

Output

Print the $M$ -th base-2 palindrome in base 10 on the first line.

Examples2

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
3
```
Expected output
```
5
```