 11

# Next smaller Palindrome

Difficulty: EASY Contributed By
Prashansa
Avg. time to solve
10 min
Success Rate
85%

Problem Statement
Suggest Edit

#### 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.

##### Note:
``````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.
``````
##### Input Format:
``````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.
``````
##### Output Format:
``````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.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 100
1 <= |S| <= 10^4

Where |S| donates the size of string 'S'.

Time Limit: 1sec
``````
##### Sample Input 1:
``````1
12321
``````
##### Sample Output 1:
``````12221
``````
##### Explanation For Sample Input 1:
``````The next smaller palindrome to 12321 is 12221, as it is strictly less than 12321 and it reads the same from the front and back both.
``````
##### Sample Input 2:
``````2
11
101
``````
##### Sample Output 2:
``````9
99
``````   Console