# Description

You are given a string s, consisting of lowercase English letters. Find the longest string, t, which satisfies the following conditions:

• The length of t does not exceed the length of s.
• t is a palindrome.
• There exists two strings a and b (possibly empty), such that t=a+b ( "+" represents concatenation), and a is prefix of s while b is suffix of s.

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.

Example
input
5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba
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".

# Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll base = 233;
const int maxn = 1e6+10;
const int mod = 1e9+7;
ll p[maxn],l[maxn],r[maxn];
bool check(ll L,ll R){
ll x,y;
x=(l[R]-l[L-1]*p[R-L+1]%mod+mod)%mod;
y=(r[L]-r[R+1]*p[R-L+1]%mod+mod)%mod;//求子串的哈希值,模板
return x==y;//如果前缀和后缀哈希值相等,说明这个子串是回文串
}
int main()
{
ios::sync_with_stdio(0);
p[0]=1;
ll t;
cin>>t;
while(t--)
{
string s;
cin>>s;
ll n=s.size();
s=" "+s;//把字符串中的字符下标置为1-n,方便处理
for(ll i=1;i<=n;i++)    l[i]=l[i-1]*base%mod+s[i],p[i]=p[i-1]*base,l[i]%=mod,p[i]%=mod;//计算前缀哈希值,p[i]为base的i次方,优化时间
for(ll i=n;i>=1;i--)    r[i]=r[i+1]*base%mod+s[i],r[i]%=mod;//计算后缀哈希值
ll pos=0;
for(ll i=1;i<=n/2;i++){
if(s[i]==s[n+1-i]){
pos=i;
}
else    break;
}//找到原字符串前后可以构建出的最长回文子串
ll flag=0,maxx=0;
for(ll i=pos+1;i<=n-pos;i++){
if(check(pos+1,i)&&i-pos>maxx){
flag=1;
maxx=i-pos;
}
}//求剩下的字符串前缀最长回文子串
for(ll i=n-pos;i>=pos+1;i--){
if(check(i,n-pos)&&n-pos-i+1>maxx){
flag=2;
maxx=n-pos-i+1;
}
}//求剩下的字符串后缀最长回文子串
/*然后输出即可*/
for(ll i=1;i<=pos;i++)    cout<<s[i];
if(flag==1){
for(ll i=pos+1;i<=pos+maxx;i++)    cout<<s[i];
}else if(flag==2){
for(ll i=n-pos-maxx+1;i<=n-pos;i++)    cout<<s[i];
}
for(ll i=n-pos+1;i<=n;i++)    cout<<s[i];
cout<<endl;
}
return 0;
}