Next Smallest Palindrome Problem Statement

Find the next smallest palindrome strictly greater than a given number 'N' represented as a string 'S'.

Explanation:

You are given a number in string format, and your task is to determine the smallest numeric palindrome that is strictly greater than the given number.

Input:

The first line contains an integer 'T', the number of test cases.
The first line for each test case includes an integer, the number of digits in 'N'.
The second line for each test case contains the string 'S'.

Output:

Return the next greater palindrome as a string for each test case.

Example:

Suppose the input is:

Input:

T = 1
N = 3
S = "123"

Output:

"131"

Explanation:

The next smallest palindrome greater than '123' is '131'.

Constraints:

• 1 <= T <= 100
• 1 <= len(S) <= 10^4

Note:

• A palindrome reads the same backward as forward, e.g., 'naman', 'abcba', '1234321'.
• The given string 'S' represents a numerical value greater than 0.
• Single-digit numbers are also considered palindromic.
• The length of 'S' is the number of digits in 'N'.
• Implementation does not require printing; only return the result.