11784: SubString

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:2 Solved:0

Description

You are given a string input.You are to find the longest substring of input such that the reversal of the substring is also a

substring of input.In case of a tie,return the string that occurs earliest in input.

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 tie-breaker rule of taking the earliest

one first.

Input

The first line of input gives a single integer,1<=N<=10,the num of test cases.

Then follow,for each test case,a line containing between 1 and 50 characters,inclusive.

Each character of input will be an uppercase letter('A'-'Z').

Output

Output for each test case the longer substring of input such that the reversal of the substring is also a substring of input.

Sample Input Copy

3
ABCABA
XYZ
XCVCX

Sample Output Copy

ABA
X
XCVCX