Given an integer k, write a program to find the closest integer (not including itself), which is a palindrome.

Problem Note

  • The 'closest' is defined as absolute difference minimized between two integers.
  • Input k is a positive integer represented by string, whose length will not exceed 15.
  • If there is a tie, return the smaller one as answer.

Example 1

Input: "123"
Output: "121"
Explanation: "121" and "131" are two nearest integer which are plaindrome. But "121" is the answer because the absolute difference is minimum between "121" and "123".