Next Palindrome Number

Time limit2sMemory limit128 MB

Summary

Given a positive integer with up to 50 digits, construct the smallest palindrome number strictly greater than it.

Level: Medium6 of 10
Topics: String, Math, Greedy, Simulation
Solved: No attempts yet

Problem

A palindrome number is a positive integer that reads the same from left to right and from right to left. 101, 4, and 6666 are palindrome numbers, while 10, 564, and 15452 are not.

Given a positive integer N, find the smallest palindrome number that is greater than N.

Input

The first line contains a positive integer N. N has at most 50 digits, and its first digit is not 0.

Output

Print the smallest palindrome number greater than N.

Examples5

Example 1
Input
```
12345
```
Expected output
```
12421
```
Example 2
Input
```
858
```
Expected output
```
868
```
Example 3
Input
```
1999
```
Expected output
```
2002
```
Example 4
Input
```
1
```
Expected output
```
2
```
Example 5
Input
```
9999
```
Expected output
```
10001
```