#include <bits/stdc++.h>
using namespace std;
int T;
string str;
int mxl;
string mxs;
int N;
int A[1000005];
int D[1000005 * 2];
int Z[1000005 * 2];
void manacher() {
  for (int i = 0; i <= N - 1; i++) {
    D[i * 2] = -1;
    D[i * 2 + 1] = (int)(str[i] - 'a');
  }
  D[N * 2] = -1;
  int n = N * 2 + 1;
  int c = 0, r = 0;
  for (int i = 0; i <= n - 1; i++) Z[i] = 0;
  for (int i = 1; i <= n - 2; i++) {
    int m = c - (i - c);
    if (r > i) Z[i] = min(r - i, Z[m]);
    while (i - Z[i] - 1 >= 0 && i + Z[i] + 1 < n &&
           D[i - Z[i] - 1] == D[i + Z[i] + 1])
      Z[i]++;
    if (i + Z[i] > r) {
      c = i;
      r = i + Z[i];
    }
  }
}
int mxp[1000005];
void build_table() {
  int n = N * 2 + 1;
  for (int i = 0; i <= N - 1; i++) mxp[i] = 0;
  for (int i = 1; i <= n - 2; i++) {
    int ln = Z[i];
    if (ln == 0) continue;
    int lid, rid;
    if (i % 2 == 0) {
      lid = (i / 2) - 1 - ln / 2 + 1;
      rid = (i / 2) + ln / 2 - 1;
    } else {
      lid = i / 2 - ln / 2;
      rid = i / 2 + ln / 2;
    }
    int dl = lid + 1, dr = N - rid;
    if (dl < dr)
      mxp[lid] = max(mxp[lid], ln);
    else if (dl > dr)
      mxp[rid] = max(mxp[rid], ln);
    else {
      mxp[lid] = max(mxp[lid], ln);
      mxp[rid] = max(mxp[rid], ln);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> T;
  while (T--) {
    cin >> str;
    N = (int)(str.size());
    mxl = 1;
    mxs = string(str.begin(), str.begin() + 1);
    int p1, p2, p3, p4;
    p1 = 0;
    p2 = 1;
    p3 = N;
    p4 = N;
    manacher();
    build_table();
    int pl, pr;
    pl = pr = 0;
    for (int i = 0; i <= N / 2 - 1; i++) {
      int l = i * 2;
      pl = max(mxp[i], pl);
      if (l + pl > mxl) {
        mxl = l + pl;
        p1 = 0, p2 = i + pl, p3 = N - i, p4 = N;
      }
      pl -= 2;
      pr = max(mxp[N - 1 - i], pr);
      if (l + pr > mxl) {
        mxl = l + pr;
        p1 = 0, p2 = i, p3 = N - i - pr, p4 = N;
      }
      pr -= 2;
      if (str[i] != str[N - 1 - i]) break;
    }
    if (mxl > 1)
      mxs = string(str.begin(), str.begin() + p2) +
            string(str.begin() + p3, str.end());
    cout << mxs << '\n';
  }
  return 0;
}
