题目描述

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.

输入格式

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 for each test case the longer substring of input such that the reversal of the substring is also a substring of input.

样例

样例 1

输入 # 1

3
ABCABA
XYZ
XCVCX

输出 # 1

ABA
X
XCVCX