Matcom Online Grader

Un entero positivo $n$ es base-b palindrome si su representación en base $b$ es un palindrome. Por ejemplo, $7$ (base $10$) es un palindrome en cualquier base mayor o igual a $8$. Es también un palindrome en base $2$ ($111$) y $6$ ($11$), pero no en base $3$ ($21$), $4$ ($13$), $5$ ($12$), o $7$ ($10$). Los primeros cuatro palindromes en base $2$ (escritos en base $10$) son $1, 3, 5$ y $7$. Es necesario que encuentres cuál es en $k$-ésimo base-2 palindrome.

Input

La entrada consiste de una única línea con un entero $k$ ($1 \le k \le 50000$), escrito en base $10$.

Output

La salida debes ser la representación en base $10$ del $k$-ésimo base-2 palindrome.

Sample test(s)