#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
const long long inf = 1e18;
long long i, j, k, m, n, qq, t, it, ma = -inf, mi = inf, x, y, col,
                                    md = 998244353;
string cmp(string second) {
  vector<long long> p(second.size(), 0);
  for (i = 1; i < second.size(); i++) {
    j = p[i - 1];
    while (j > 0 && second[i] != second[j]) j = p[j - 1];
    if (second[i] == second[j]) j++;
    p[i] = j;
  }
  return second.substr(0, j);
}
int32_t main() {
  cin >> qq;
  while (qq--) {
    string second;
    cin >> second;
    n = second.size();
    k = 0;
    while (n - 1 - k >= 0 && k < n / 2 && second[k] == second[n - 1 - k]) k++;
    if (k == (n + 1) / 2) {
      cout << second << '\n';
      continue;
    }
    for (i = 0; i < k; i++) cout << second[i];
    string t = second.substr(k, max(0ll, n - k - k));
    string rt = t;
    reverse(rt.begin(), rt.end());
    string ans1 = cmp(t + "%" + rt);
    string ans2 = cmp(rt + "%" + t);
    if (ans1.size() > ans2.size())
      cout << ans1;
    else
      cout << ans2;
    for (i = k - 1; i > -1; i--) cout << second[i];
    cout << '\n';
  }
  return 0;
}
