#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 2e6 + 5;
string pr;
int calc() {
  vector<int> z(pr.length());
  int j = 0;
  for (int i = (1); i < (pr.length()); i++) {
    while (j > 0 && pr[i] != pr[j]) j = z[j - 1];
    if (pr[i] == pr[j]) j++;
    z[i] = j;
  }
  return j;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int l = s.length();
    int k = 0;
    for (int i = (0); i < (l / 2); i++) {
      if (s[i] == s[l - 1 - i])
        k++;
      else
        break;
    }
    string sp = string(s, k, l - 2 * k), ps;
    ps = sp;
    reverse(ps.begin(), ps.end());
    pr = sp + '!' + ps;
    int ans = calc();
    string ansstr = string(pr, 0, ans);
    pr = ps + '!' + sp;
    int tp = calc();
    for (int i = (0); i < (k); i++) {
      cout << s[i];
    }
    if (ans > tp)
      cout << ansstr;
    else
      cout << string(pr, 0, tp);
    for (int i = (k - 1); i >= (0); i--) cout << s[i];
    cout << endl;
  }
  return 0;
}
