前后缀回文（困难版）

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个仅由小写英文字母组成的非空字符串 $s$。请找出最长的字符串 $r$，满足：

• $r$ 的长度不超过 $s$ 的长度；
• $r$ 是回文串；
• 存在两个可以为空的字符串 $a,b$，使得 $r=a+b$，其中 $a$ 是 $s$ 的前缀，$b$ 是 $s$ 的后缀。

输入格式

第一行包含一个整数 $T$，表示测试用例数。

接下来 $T$ 行，每行包含一个非空字符串 $s$，字符串仅由小写英文字母组成。

输出格式

对于每个测试用例输出一行，给出满足条件的最长字符串。如果有多个最长答案，输出任意一个即可。

样例输入 1

5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba

样例输出 1

a
abcdfdcba
xyzyx
c
abba

样例解释

对于 abcdfdcecba，abcdfdcba 是一个最长合法答案。对于 codeforces，c 和 s 都是合法答案。

数据范围

对于所有数据，$1\le T\le 10^5$，所有字符串的长度之和不超过 $10^6$。