Prefix-Suffix Palindrome (Hard version)

Description:

Input:

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$), the number of test cases. The next $$$t$$$ lines each describe a test case.

Each test case is a non-empty string $$$s$$$, consisting of lowercase English letters.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed $$$10^6$$$.

Output:

For each test case, print the longest string which satisfies the conditions described above. If there exists multiple possible solutions, print any of them.

Sample Input:

5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba

Sample Output:

a
abcdfdcba
xyzyx
c
abba

Note:

In the first test, the string $$$s = $$$"a" satisfies all conditions.

In the second test, the string "abcdfdcba" satisfies all conditions, because:

• Its length is $$$9$$$, which does not exceed the length of the string $$$s$$$, which equals $$$11$$$.
• It is a palindrome.
• "abcdfdcba" $$$=$$$ "abcdfdc" $$$+$$$ "ba", and "abcdfdc" is a prefix of $$$s$$$ while "ba" is a suffix of $$$s$$$.

It can be proven that there does not exist a longer string which satisfies the conditions.

In the fourth test, the string "c" is correct, because "c" $$$=$$$ "c" $$$+$$$ "" and $$$a$$$ or $$$b$$$ can be empty. The other possible solution for this test is "s".