#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int M = 2e6 + 7;
const int lim = 2e6;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int a[M];
string fun(string s) {
  string ss = s;
  reverse(ss.begin(), ss.end());
  ss = s + "#" + ss;
  int k = 0, len = ss.size();
  for (int i = 1; i < len; i++) {
    while (k != 0 && ss[k] != ss[i]) k = a[k - 1];
    if (ss[k] == ss[i]) k++;
    a[i] = k;
  }
  return s.substr(0, k);
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    string s;
    cin >> s;
    int len = s.size(), l = 0, r = len - 1;
    while (l < r && s[l] == s[r]) l++, r--;
    if (l > 0) cout << s.substr(0, l);
    if (len > 2 * l) {
      string t = s.substr(l, len - 2 * l);
      string aa = fun(t);
      reverse(t.begin(), t.end());
      string bb = fun(t);
      if (aa.length() < bb.length()) swap(aa, bb);
      cout << aa;
    }
    if (l > 0) cout << s.substr(len - l, l);
    printf("\n");
  }
  return 0;
}
