#include <bits/stdc++.h>
using namespace std;
const long long p = 53;
const long long mod = 2000000011;
map<long long, set<long long> > ind;
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long q;
  cin >> q;
  for (long long i = 0; i < q; ++i) {
    string s;
    cin >> s;
    long long l = 0, r = s.size() - 1;
    string ans;
    while (l < r && s[l] == s[r]) {
      ans += s[l];
      l += 1;
      r -= 1;
    }
    string st;
    long long lk = l;
    while (lk <= r) {
      st += s[lk];
      lk += 1;
    }
    string stroka = st;
    reverse(st.begin(), st.end());
    string stroka2 = st;
    stroka2 += stroka;
    stroka += st;
    long long l1 = 0, r1 = 0;
    vector<long long> z(stroka.size(), 0);
    for (long long j = 1; j < stroka.size(); ++j) {
      if (j <= r1) {
        z[j] = min(z[j - l1], r1 - j + 1);
      }
      while (j + z[j] < stroka.size() && stroka[j + z[j]] == stroka[z[j]]) {
        z[j] += 1;
      }
      if (j + z[j] - 1 > r1) {
        r1 = j + z[j] - 1;
        l1 = j;
      }
    }
    string ans2;
    long long y = z.size() / 2;
    while (y < z.size()) {
      if (y + z[y] == z.size()) {
        while (y < z.size()) {
          ans2 += stroka[y];
          y += 1;
        }
        break;
      }
      y += 1;
    }
    string v1 = ans;
    v1 += ans2;
    reverse(ans.begin(), ans.end());
    v1 += ans;
    long long l2 = 0, r2 = 0;
    vector<long long> z2(stroka2.size(), 0);
    for (long long j = 1; j < stroka.size(); ++j) {
      if (j <= r2) {
        z2[j] = min(z2[j - l2], r2 - j + 1);
      }
      while (j + z2[j] < stroka2.size() &&
             stroka2[j + z2[j]] == stroka2[z2[j]]) {
        z2[j] += 1;
      }
      if (j + z2[j] - 1 > r2) {
        r2 = j + z2[j] - 1;
        l2 = j;
      }
    }
    string ans3;
    y = z.size() / 2;
    while (y < z.size()) {
      if (y + z2[y] == z2.size()) {
        while (y < z2.size()) {
          ans3 += stroka2[y];
          y += 1;
        }
        break;
      }
      y += 1;
    }
    string v2 = ans;
    v2 = ans3 + ans;
    reverse(ans.begin(), ans.end());
    v2 = ans + v2;
    if (v2.size() > v1.size()) {
      cout << v2 << "\n";
    } else {
      cout << v1 << "\n";
    }
  }
}
