#include <bits/stdc++.h>
using namespace std;
char s[5000005], t[5000005];
int pos;
int f[5000005];
int main() {
  int m;
  cin >> m;
  while (m--) {
    cin >> s;
    t[0] = t[1] = '#';
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
      t[2 * i + 2] = s[i];
      t[2 * i + 3] = '#';
    }
    t[2 * len + 2] = 0;
    int l, r;
    len = strlen(t + 1), l = 1, r = len;
    while (l <= r) {
      if (t[l] == t[r])
        l++, r--;
      else
        break;
    }
    int ans = 0, nl = l, nr = l, maxr = l, pos = l;
    for (int i = l; i <= r; i++) {
      if (i < maxr)
        f[i] = min(maxr - i, f[(pos << 1) - i]);
      else
        f[i] = 1;
      while (t[i + f[i]] == t[i - f[i]] && i + f[i] <= r && i - f[i] >= l)
        f[i]++;
      if (f[i] + i > maxr) {
        maxr = f[i] + i;
        pos = i;
      }
      if ((i - f[i] < l || i + f[i] > r) && f[i] > ans) {
        nl = i - f[i] + 1;
        nr = i + f[i] - 1;
        ans = f[i];
      }
    }
    if (l > r) {
      cout << s << endl;
      continue;
    }
    for (int i = 1; i < l; i++)
      if (t[i] != '#') cout << t[i];
    for (int i = nl; i <= nr; i++)
      if (t[i] != '#') cout << t[i];
    for (int i = r + 1; i <= len; i++)
      if (t[i] != '#') cout << t[i];
    cout << endl;
  }
  return 0;
}
