#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const long long mod = 1e9 + 7;
const long long maxn = 2e6 + 10;
long long p[2] = {1000000007, 998244353};
long long seed[2] = {500000004, 500000004};
int tt, n, k;
string s;
char t[maxn * 2];
int pos = 0, maxright = 0, maxlen = 0, r[maxn * 2], mxlen;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> tt;
  while (tt > 0) {
    tt--;
    cin >> s;
    n = s.length();
    int flag = 0;
    for (int i = 0; i <= n - 1 - i; i++) {
      if (i >= n - 1 - i) {
        flag = 1;
        break;
      }
      if (s[i] != s[n - 1 - i]) break;
    }
    if (flag == 1) {
      cout << s << endl;
      continue;
    }
    for (int i = 0; i < n; i++) {
      t[2 * i] = '#';
      t[2 * i + 1] = s[i];
    }
    t[2 * n] = '#';
    for (int i = 0; i <= 2 * n; i++) r[i] = 0;
    pos = 0;
    maxright = 0;
    maxlen = 0;
    for (int i = 0; i <= 2 * n; i++) {
      if (i < maxright)
        r[i] = min(r[2 * pos - i], maxright - i);
      else
        r[i] = 1;
      while (i - r[i] >= 0 && i + r[i] <= 2 * n && t[i - r[i]] == t[i + r[i]])
        r[i]++;
      if (r[i] + i - 1 > maxright) {
        maxright = r[i] + i - 1;
        pos = i;
      }
    }
    mxlen = 0;
    for (int i = 0; i < n; i++) {
      if (t[i] == t[2 * n - i]) {
        mxlen++;
      } else {
        break;
      }
    }
    int ans = 1, al = 1, ar = 0;
    if (mxlen >= 2) {
      ans = mxlen / 2 * 2;
      al = ar = mxlen / 2;
    }
    for (int i = 0; i <= 2 * n; i++) {
      int ls, x, y;
      if (i + r[i] - 1 + mxlen >= 2 * n &&
          2 * n - (i + r[i] - 1) <= i - r[i] + 1) {
        ls = r[i] / 2 * 2 - i % 2 + (2 * n - (i + r[i] - 1)) / 2 * 2;
        if (ls > ans && ls <= n) {
          ans = ls;
          ar = r[i] / 2 * 2 - i % 2 + (2 * n - (i + r[i] - 1)) / 2;
          al = (2 * n - (i + r[i] - 1)) / 2;
        }
      }
      if (i - r[i] + 1 - mxlen <= 0 && i - r[i] + 1 <= 2 * n - (i + r[i] - 1)) {
        ls = r[i] / 2 * 2 - i % 2 + (i - r[i] + 1) / 2 * 2;
        if (ls > ans && ls <= n) {
          ans = ls;
          al = r[i] / 2 * 2 - i % 2 + (i - r[i] + 1) / 2;
          ar = (i - r[i] + 1) / 2;
        }
      }
    }
    for (int i = 0; i < al; i++) cout << s[i];
    for (int i = n - ar; i < n; i++) cout << s[i];
    cout << endl;
  }
  return 0;
}
