#include <bits/stdc++.h>
using namespace std;
int f[2000010];
int prefix(string s) {
  s += '#' + string(s.rbegin(), s.rend());
  int k = 0;
  for (int i = 1; i < s.size(); i++) {
    while (k && s[i] != s[k]) k = f[k];
    if (s[i] == s[k]) k++;
    f[i + 1] = k;
  }
  return k;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int i, j, k, l, m, n, t, p, e;
  string s, rem;
  cin >> t;
  while (t--) {
    l = 0;
    cin >> s;
    n = s.size();
    for (i = 0, j = n - 1; i < n / 2; i++, j--) {
      if (s[i] == s[j])
        l = i + 1;
      else
        break;
    }
    rem = s.substr(l, n - 2 * l);
    p = prefix(rem);
    e = prefix(string(rem.rbegin(), rem.rend()));
    if (p > e)
      cout << s.substr(0, l) + s.substr(l, p) + s.substr(n - l) << endl;
    else
      cout << s.substr(0, l) + s.substr(s.size() - l - e) << endl;
  }
  return 0;
}
