// Problem: D2. Prefix-Suffix Palindrome (Hard version)
// Contest: Codeforces Global Round 7
// Coder: kimi2011
// URL: https://codeforces.com/contest/1326/problem/D2
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
#define debug(x) cerr << #x << " " << x << '\n';
#define multi true
using namespace std;
const int p1 = 100000007;
const int p2 = 1000000007;
const int N = 1e6 + 10;
int t = 1, n, ans;
int hash1[N], hash2[N], fhash1[N], fhash2[N], P1[N] = {1}, P2[N] = {1};
string s, t1, t2;
int mod (int x, int p) {return (x % p + p) % p;}
int Hash1(int l, int r) {return mod(hash1[r] - hash1[l - 1] * P1[r - l + 1], p1);}
// int Hash2(int l, int r) {return mod(hash2[r] - hash2[l - 1] * P2[r - l + 1], p2);}
int Fhash1(int l, int r) {return mod(fhash1[l] - fhash1[r + 1] * P1[r - l], p1);}
// int Fhash2(int l, int r) {return mod(fhash2[l] - fhash2[r + 1] * P2[r - l], p2);}
void solve() {
    cin >> s;
    n = s.size(), s = " " + s;
    for (int i = 1; i <= n / 2 + 1; i++) {
    	if (s[i] != s[n - i + 1] || i == n / 2 + 1) {
    		t1 = s.substr(1, i - 1);
    		t2 = s.substr(n - i + 2, i);
    		s = s.substr(i, n - 2 * i + 2);
    		ans = n - s.size();
    		n = s.size();
    		break;
    	}
    }
	cout << '[' << t1 << "],[" << t2 << "]\n";
	cout << '[' << s << "]\n";
    s = " " + s;
    for (int i = 1; i <= n; i++) hash1[i] = (hash1[i - 1] * p1 + s[i] - 'a') % p1;
    for (int i = 1; i <= n; i++) hash2[i] = (hash2[i - 1] * p2 + s[i] - 'a') % p2;
    for (int i = n; i >= 1; i--) fhash1[i] = (fhash1[i + 1] * p1 + s[i] - 'a') % p1;
    for (int i = n; i >= 1; i--) fhash2[i] = (fhash2[i + 1] * p2 + s[i] - 'a') % p2;
    for (int i = 1; i <= n; i++) P1[i] = P1[i] * 30 % p1;
    for (int i = 1; i <= n; i++) P2[i] = P2[i] * 30 % p2;
	int ans1 = 0, ans2 = 0;
	for (int i = 1; i <= n; i++) if (Hash1(i, n) == Fhash1(i, n)/* && Hash2(i, n) == Fhash2(i, n)*/) {ans1 = n - i + 1; break;}
	for (int i = n; i >= 1; i--) if (Hash1(1, i) == Fhash1(1, i)/* && Hash2(1, i) == Fhash2(1, i)*/) {ans2 = i; break;} 
	
	if (ans1 >= ans2) {
		cout << t1;
		for (int i = n - ans1 + 1; i <= n; i++) cout << s[i];
		cout << t2 << '\n';
	} else {
		cout << t1;
		for (int i = 1; i <= ans2; i++) cout << s[i];
		cout << t2 << '\n';
	}
    return;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (multi) cin >> t;
    while (t--) solve();
    return 0;
}