Given an integer num , write a program to find the closest palindrome to integer num . (excluding num ). The output need not be larger than num . It can be smaller or larger than num .

Problem Note

  • An integer is said to be a palindrome if it remains the same when its digits are reserved.
  • 'Closest' means that the absolute difference between two integers should be minimum.
  • num is a positive integer represented by a string, whose length will not exceed 15 digits.
  • If two palindromic integers are closest to num and there is a tie between them, then return the smaller one as output.

Example 1

Input: "99"
Output: "101"
Explanation: "88" and "101" are two nearest integers which are palindrome. But "101" is the answer because the absolute difference is minimum between "99" and "101".