Given a string s, find the longest palindrome substring in s.

If there are multiple valid substrings, find the first one.

Example

s: “mississippi”

Longest palindrome substring: “ississi”

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.

For each test case, the input has one line with the string ‘s’.

Output Format

For each test case, the output has one line with string ‘p’ denoting the longest palindrome substring.

Sample Input

5
mississippi
avcccvbgf
abcdc
a
abc

Expected Output

ississi
vcccv
cdc
a
a

Constraints

1 <= T <= 100
1 <= n <= 1000
Characters of string are lowercase English characters.