#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
using namespace std;
int t, v[2000005];
string second;
string solve(string x) {
  string idk = x;
  reverse(idk.begin(), idk.end());
  x = x + "#" + idk;
  int pos = 0;
  for (int i = 1; i < x.size(); i++) {
    while (pos != 0 && x[i] != x[pos]) {
      pos = v[pos - 1];
    }
    if (x[pos] == x[i]) {
      pos++;
      v[i] = pos;
    }
  }
  return x.substr(0, pos);
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> t;
  while (t--) {
    cin >> second;
    int l = 0, r = second.size() - 1;
    int verif = -1;
    while (l <= r) {
      if (l == r) {
        verif = 1;
        break;
      } else if (second[l] == second[r]) {
        l++;
        r--;
      } else
        break;
    }
    if (verif == 1) {
      cout << second << '\n';
      continue;
    }
    string b = "";
    b = second.substr(l, r - l + 1);
    string ans1 = solve(b);
    reverse(b.begin(), b.end());
    string ans2 = solve(b);
    if (ans2.size() > ans1.size()) {
      ans1 = ans2;
    }
    string ans = second.substr(0, l);
    cout << ans;
    reverse(ans.begin(), ans.end());
    cout << ans1;
    cout << ans << '\n';
  }
}
