LTAI-22-01-16

#### Start

2022-01-11 04:00 AKST

## LTAI-22-01-16

#### End

2022-01-16 09:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -134 days 5:43:19

125:00:00

0:00:00

# Problem HBase-2 Palindromes

A positive integer $N$ is a base-$b$ palindrome if the base-$b$ representation of $N$ (with no leading zeros) is a palindrome, i.e. reads the same way in either direction. For instance, $7$ (base $10$) is a palindrome in any base greater than or equal to $8$. It is also a palindrome in base $2$ ($111$) and $6$ ($11$), but not in $3$ ($21$), $4$ ($13$), $5$ ($12$), or $7$ ($10$). The first four base-$2$ palindromes (written in base $10$) are $1$, $3$, $5$, and $7$.

You are supposed to find the $M$-th base-$2$ palindrome and output its base-$10$ representation.

## Input

The input is a single line with a single positive integer $M\leq 50\, 000$ in base $10$.

## Output

The output for input $M$ should be a single line with the base-$10$ representation of the $M$-th base-$2$ palindrome.

Sample Input 1 Sample Output 1
1

1

Sample Input 2 Sample Output 2
3

5