#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

A palindrome is defined as a string that reads the same forward and backward. For example, RAR is a palindrome while SAM and PEANUT is not. Any single character string is a palindrome.

A palindromic number is a number that is a palindrome. Hence, it is a number that reads the same forward or backwards. For instance, 2, 3, 11, 22, 131, 1991 are palindromic numbers.

Rar the Cat is interested in the **N**-smallest palindromic number and wants you to find out what is it.

## Input

The first line of input will contain one integer, **N**.

## Output

The output should contain one integer, the **N**-smallest palindromic number.

## Limits

Subtask 1 (24%): 1 ≤ **N** < 2000. In addition, the answer is guaranteed to be lower than 10^{6}

Subtask 2 (27%): 1 ≤ **N** ≤ 10^{6}.

Subtask 3 (33%): 1 ≤ **N** ≤ 10^{9}.

Subtask 4 (16%): 1 ≤ **N** ≤ 10^{18}.

Subtask 5 (0%): Sample Testcases

## Sample Testcase 1

### Input

3

### Output

2

### Explanation

The first three palindromic numbers are 0, 1 and 2.

## Sample Testcase 2

### Input

12

### Output

22

### Explanation

The first 12 palindromic numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 24 | 23 | 0.5s | 256MB | Minimum |

2 | 27 | 55 | 0.5s | 256MB | Minimum |

3 | 33 | 89 | 0.5s | 256MB | Minimum |

4 | 16 | 157 | 0.5s | 256MB | Minimum |

5 | 0 | 2 | 0.5s | 256MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o palindromicnumber -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512