Find the Next Smaller Palindrome

You are provided with a number N, expressed as a string S, which is a palindrome. The task is to determine the largest number strictly less than N that is also a palindrome.

Example

Input:

T = 1
S = "12321"

Output:

"12221"

Input

The first line contains an integer T, representing the number of test cases.

For each test case, there is a single line containing the string S, which is the number for which the next smaller palindrome is to be determined.

Output

For each test case, output a single line containing the next smaller palindrome of S.

Constraints

• 1 <= T <= 100
• 1 <= |S| <= 10^4
• The input string S represents a number greater than 0.

Note

• A palindrome reads the same backward as forward; e.g., madam, racecar, 1234321.
• Single-digit numbers are considered palindromes.
• The resulting palindrome should not have leading zeros, except when the result is 0.