Longest Palindromic Substring

You are given a non-empty string s. Your task is to find the longest palindromic substring within s. In case there are multiple palindromic substrings of maximum length, output the lexicographically smallest one.

A palindrome is a string that reads the same backward as forward. The expected solution should efficiently check each character (and pair of adjacent characters) as the center of potential palindromes and expand outward from it.

The formula for expanding around the center can be illustrated in LaTeX as follows:

\(expand(s, i, j) : \text{while } i \ge 0 \text{ and } j < |s| \text{ and } s[i] = s[j], \text{ increment } j \text{ and decrement } i\)

Finally, the longest palindrome is chosen based on the maximum length first; if lengths are equal, the lexicographically smaller one is chosen.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each of the next \(T\) lines contains a non-empty string s.

Input Format:

T
s1
s2
...
sT

outputFormat

For each test case, output the longest palindromic substring on a separate line.

Output Format:

result1
result2
...
resultT

## sample

3
babad
cbbd
aacabdkacaa

bab
bb
aca

</p>