#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-9;
const long double pi = acos(-1);
const int mod = 998244353;
const int mod1 = 1e9 + 7;
mt19937_64 rnd(time(0));
void faster() {
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
}
vector<long long> d1;
vector<long long> d2;
void calc(string &s) {
  long long n = ((long long)(s).size());
  long long l = 0, r = -1;
  for (int i = 0; i < n; i++) {
    long long k = 0;
    if (i <= r) {
      k = min(r - i, d1[r - i + l]);
    }
    while (i + k + 1 < n && i - k - 1 >= 0 && s[i + k + 1] == s[i - k - 1]) {
      k++;
    }
    d1[i] = k;
    if (i + k > r) {
      l = i - k;
      r = i + k;
    }
  }
  l = 0;
  r = -1;
  for (int i = 0; i < n; i++) {
    long long k = 0;
    if (i <= r) {
      k = min(r - i + 1, d2[r - i + l + 1]);
    }
    while (i + k < n && i - k - 1 >= 0 && s[i + k] == s[i - k - 1]) k++;
    d2[i] = k;
    if (i + k - 1 > r) {
      l = i - k;
      r = i + k - 1;
    }
  }
}
signed main() {
  faster();
  double start = clock();
  long long t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    long long n = ((long long)(s).size());
    d1.assign(((long long)(s).size()), 0);
    d2.assign(((long long)(s).size()), 0);
    long long l = 0, r = n - 1, maxl = 0, minr = n - 1;
    calc(s);
    while (s[l] == s[r]) {
      l++;
      r--;
      maxl = l;
      minr = r;
      if (l == n) break;
    }
    long long maxn = 0, id = -1, ok = 0, la = 0;
    for (int i = 0; i < n; i++) {
      long long t = d1[i];
      if (maxl > i - t - 1 || minr < i + t + 1) {
        long long a = min(maxl, max({0ll, min(i - t, n - i - t - 1)}));
        if (a * 2 + t * 2 + 1 > maxn) {
          maxn = a * 2 + t * 2 + 1;
          ok = -1;
          id = i;
          la = a;
        }
      }
      t = d2[i];
      if (maxl > i - t - 1 || minr < i + t) {
        long long a = min(maxl, max({0ll, min(i - t, n - i - t)}));
        if (a * 2 + t * 2 > maxn) {
          maxn = a * 2 + t * 2;
          ok = 1;
          id = i;
          la = a;
        }
      }
    }
    if (ok == -1) {
      long long t = d1[id];
      cout << s.substr(0, la) << s.substr(id - t, t * 2 + 1)
           << s.substr(n - la);
    } else {
      long long t = d2[id];
      cout << s.substr(0, la) << s.substr(id - t, t * 2) << s.substr(n - la);
    }
    cout << endl;
  }
  cerr << "Time " << (clock() - start) * 1.0 / CLOCKS_PER_SEC << "s\n";
  return 0;
}
