Next Smaller Palindrome Problem Statement

You are provided with a palindrome number 'N' presented as a string 'S'. The task is to determine the largest palindrome number that is strictly less than 'N'.

Input:

The first line contains an integer T, the number of test cases.
For each test case, there is one line with a string 'S' which represents the palindrome number.

Output:

For each test case, output a single line containing the string representation of the largest palindrome that is less than 'S'.

Example:

Input:

T = 2
S = '12321'
S = '1000'

Output:

'12221'
'999'

Constraints:

• 1 <= T <= 100
• 1 <= |S| <= 104 (where |S| denotes the length of the string S)
• The numerical value of 'S' is greater than 0.

Note:

• A palindrome reads the same backward as forward, such as madam, racecar, 1234321.
• A single-digit number is a palindrome.
• The resulting number should not start with leading zeros, except when the answer is 0.