The problem is pretty easy, giving you a very long string, you have to find the first longest palindrome in the string. (Case-insensitive)

First line contain a integer T (T <= 100), means the test case.
And the following T lines, for each line, there is a string is make up with the uppercase and lowercase.
The string's length is less than 10000.

For each test case, you should print the longest palindrome, if there are muti-case, print first of them.