Longest Palindromic Substring

Given a string \( s \), your task is to find its longest palindromic substring. A palindrome is defined as a string that reads the same backward as forward (i.e. \( s = s^R \)). For example, in the string "babad", both "bab" and "aba" are valid answers. In cases where there are multiple valid answers, any one of them is acceptable.

You are required to process multiple test cases. The input will be given via standard input, where the first line contains an integer \( T \) (the number of test cases) and the following \( T \) lines each contain a string \( s \). For each test case, print the result on a separate line to standard output.

Note: A substring is a contiguous subsequence of characters and should be computed in \( O(n^2) \) or better time complexity for each case.

inputFormat

The first line contains an integer \( T \) representing the number of test cases. Each of the following \( T \) lines contains a non-empty string \( s \), for which you have to find the longest palindromic substring.

outputFormat

For each test case, output the longest palindromic substring on a new line. If there are multiple answers, you may output any one of them.

## sample

3
babad
cbbd
a

bab
bb
a

</p>