1635 : SUBSTRING

时间限制:1 Sec 内存限制:128 MiB
提交:56 答案正确:20

提交 状态 讨论区

题目描述

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

样例输入

复制
3                   
ABCABA
XYZ
XCVCX

样例输出

复制
ABA
X
XCVCX

提示


			

来源

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