Longest Palindromic Substring

You are given a string s. Your task is to find the longest substring of s that is a palindrome. A palindrome is a string that reads the same forward and backward. Formally, a substring \( s[i \ldots j] \) is a palindrome if:

\( s[i \ldots j] = \text{reverse}(s[i \ldots j]) \)

If there are multiple answers, output the one found by the algorithm described below. In this problem, the solution must process multiple test cases.

inputFormat

The first line contains an integer t denoting the number of test cases. Each of the following t lines contains a non-empty string s.

Note: The input is given via standard input (stdin).

outputFormat

For each test case, print the longest palindromic substring in a single line to standard output (stdout).

## sample

4
babad
cbbd
forgeeksskeegfor
a

bab
bb
geeksskeeg
a

</p>