题目描述

给定一个字符串 $S$ , 要求出一个字符串 $C$ 满足以下条件:

$C$ 是 $S$ 的非空子串(可以等于 $S$ );

$S$ 的开头为反转的 $C$ ;

$C$ 为满足上述条件的最长子串.

输入格式

第一行一个字母 $T$ ,表示子任务数量

以下 $T$ 行, 每行一个由小写英文字母构成的字符串 $S$

输出格式:

每个子任务输出一行一个字符串 $C$

数据规模:

$1$ $\le$ $T$ $\le$ $150$

$1$ $\le$ $S$ $\le$ $1000000$