HZNUOJ

SUBSTRING

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission:62     AC:22     Score:98.44

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 number 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 longest substring of input such that the reversal of the substring is also a substring of input.

Samples

input
3 ABCABA XYZ XCVCX
output
ABA X XCVCX

Source

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