103633: [Atcoder]ABC363 D - Palindromic Number

Problem Statement

A non-negative integer $X$ is called a palindrome number if its decimal representation (without leading zeros) is a palindrome.
For example, $363$, $12344321$, and $0$ are all palindrome numbers.

Find the $N$-th smallest palindrome number.

Constraints

• $1 \leq N \leq 10^{18}$
• $N$ is an integer.

Input

The input is given from Standard Input in the following format:

$N$

Output

Print the $N$-th smallest palindrome number.

Sample Input 1

46

Sample Output 1

363

The 46th smallest palindrome number is $363$.

Sample Input 2

1

Sample Output 2

0

Sample Input 3

1000000000000000000

Sample Output 3

90000000000000000000000000000000009