You are given a number 'N' in the form of a string 'S', which is a palindrome. You need to find the greatest number strictly less than 'N' which is also a palindrome.
1. A palindrome is a word, number, phrase, or another sequence of characters that reads the same backward as forward, such as madam, racecar, 1234321, etc.
2. The numerical value of the given string S will be greater than 0.
3. A single-digit number is also considered a palindrome.
4. The answer number should not contain any leading zeros, except for the case when the answer is 0.
5. Note that the length of the string is nothing but the number of digits in N.
The first line of the input contains an integer T denoting the number of test cases.
The first and the only line of each test case contains a string 'S', denoting the number whose next smaller palindrome is to be found.
The only line of output of each test case should contain a string, denoting the next smaller palindrome of 'S'.
Output for each test case will be printed in a separate line.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 100
1 <= |S| <= 10^4
Where |S| donates the size of string 'S'.
Time Limit: 1sec