You are given a stringinput. You are to find the longest substring ofinputsuch that the reversal of the

substring is also a substring ofinput. In case of a tie, return the string that occurs earliest ininput.

Note well:The substring and its reversal may overlap partially or completely. The entire original string

is itself a valid substring .

The best we can do is find a one character substring, so we implement the tiebreaker rule of taking the

earliest one first.

The first line of input gives a single integer, 1 ≤ N ≤ 10, the number of test cases. Then follow, for each

test case, a line containing between 1 and 50 characters, inclusive. Each character ofinputwill be an

uppercase letter ('A'-'Z').

Output for each test case the longest substring ofinputsuch that the reversal of the substring is also a

substring ofinput

第四届河南省大学生程序设计竞赛