B-A'6

#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
#define forn(i, a, b, delta) for (ll i = a; i < b; i += delta)
#define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr)
#pragma warning(disable : 4996)
using ll = long long;
const ll k1 = 41, mod1 = (int)1e9 + 7;
const ll k2 = 31, mod2 = (int)1e9 + 7;
vector<ll> pow1, pow2;
bool pow_calc = false;

auto produce_hash(string s) {
    const ll n = s.length();
    if (!pow_calc) {
        pow1.resize(1e6 + 1);
        pow2.resize(1e6 + 1);
        pow1[1] = 1;
        pow2[1] = 1;
        forn(i, 2, 1e6 + 1, 1) {
            pow1[i] = (pow1[i - 1] * k1) % mod1;
            pow2[i] = (pow2[i - 1] * k2) % mod2;
        }
        pow_calc = true;
    }
    vector<ll> hash1(n + 1);
    vector<ll> hash2(n + 1);
    hash1[1] = s[0];
    hash2[1] = s[0];
    forn(i, 2, n + 1, 1) {
        hash2[i] = (s[i - 1] * pow2[i] + hash2[i - 1]) % mod2;
        hash1[i] = (s[i - 1] * pow1[i] + hash1[i - 1]) % mod1;
    }
    return pair{hash1, hash2};
}

auto get_hash(const vector<ll>& hash1, const vector<ll>& hash2, ll left, ll right) {
    //[left; righ] hash 'moved' to the rigth
    //left and right in [1,2,3,4,..., s.length()]
    ll res1 = (hash1[right] - hash1[left - 1] + mod1) % mod1;
    ll res2 = (hash2[right] - hash2[left - 1] + mod2) % mod2;
    res1 = (res1 * pow1[hash1.size() - right]) % mod1;
    res2 = (res2 * pow2[hash2.size() - right]) % mod2;
    return pair {res1, res2};
}

string prefix(string str) {
    auto[left_h1, left_h2] = produce_hash(str);
    reverse(all(str));
    auto[right_h1, right_h2] = produce_hash(str);
    reverse(all(str));
    ll ans = 0;
    forn(i, 0, str.length(), 1) {
        //is [0; i] <=> [i; 0]
        auto left = get_hash(left_h1, left_h2, 1, i + 1);
        auto right = get_hash(right_h1, right_h2, str.length() - i, str.length());
        if (left == right) {
            ans = i + 1;
        }
    }
    return string(str.begin(), str.begin() + ans);
}

string mid(string str) {
    if (str[0] != str.back()) return "";
    ll bothlen = 1;
    while (bothlen * 2 < str.length()) {
        if (str[bothlen] != str[str.length() - 1 - bothlen]) break;
        bothlen += 1;
    }
    if (bothlen * 2 >= str.length()) return "";
    string pref(str.begin() + bothlen, str.end() - bothlen);
    auto post = string(pref.rbegin(), pref.rend());
    pref = prefix(pref);
    post = prefix(post);
    reverse(all(post));
    string s11 = string(str.begin(), str.begin() + bothlen) + pref, s12(str.end() - bothlen, str.end()),
            s21(str.begin(), str.begin() + bothlen), s22 = post + string(str.end() - bothlen, str.end());
    string res1 = s11 + s12, res2 = s21 + s22;
    return res1.length() > res2.length() ? res1 : res2;
}

void solve() {
    string str; cin >> str;
    string rstr = str; reverse(all(rstr));
    string ans1, ans2, ans3;
    ans1 = mid(str);
    ans2 = prefix(str);
    ans3 = prefix(rstr);
    vector<string> answers = { ans1, ans2, ans3 };
    string ans = *max_element(all(answers), [](const string& a, const string& b) { return a.length() < b.length(); });
    //cerr << "Answer:       ";
    cout << ans << '\n';
}


int main() {
    FAST;
    //freopen("output.txt", "w", stdout);
    //freopen("input.txt", "r", stdin);
    int t; cin >> t;
    while (t--) {
        solve();
    }
}