题目描述

这是本题的困难版。 区别在于对字符串长度总和和多测数量的限制。

给你一个由小写英文字母组成的字符串 $s$。找出满足以下条件的最长字符串 $t$：

• $t$ 的长度不超过 $s$ 的长度。
• $t$ 是一个回文字符串。
• 存在两个字符串 $a$ 和 $b$（可能为空，且 $a$ 和 $b$ 不相交），使得 $t=a+b$ （加号表示连接），并且 $a$ 是 $s$ 的前缀，$b$ 是 $s$ 的后缀。

输入格式

输入由多个测试样例组成。第一行包含一个整数 $t$（ $1\le t\le 10^5$），即测试样例的数量。接下来的 $t$ 行分别描述一个测试样例。

每组数据的第一行都是一个非空字符串 $s$，且仅由小写英文字母组成。

保证所有测试样例的字符串长度之和不超过 $10^6$。

输出格式

对于每个测试样例，打印满足上述条件的最长字符串。 如果存在多个可能的解决方案，则打印其中任何一个。

说明/提示

在第一个样例中，字符串 a 满足所有条件。

在第二个样例中，字符串 abcdfdcba 满足所有条件。

• 因为它的长度是 $9$，没有超过字符串 $s$ 的长度 $11$。
• 它是一个回文串。
• abcdfdcba=abcdfdc+ba，abcdfdc 是 $s$ 的前缀，而 ba 是 $s$ 的后缀。

可以证明，不存在满足条件的更长字符串。

在第四次样例中，字符串 c 是正确的，因为 c=c +""(即空串)，又因为 $a$ 或 $b$ 可以为空。 这个样例的另一个可能解法是 s。

样例

5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba

a
abcdfdcba
xyzyx
c
abba