#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const double pi = 2 * acos(0.0);
long long a1, a2, a3, b1, b2, b3, c, c1, c2, c3, d, d1, d2, d3, d4, d5, e1, e2,
    e3, f, h, k, l, m, n, m1, m2, n1, n2, o, p, p1, p2, p3, p4, q, q1, q2, q3,
    q4, s, t, u, x, y, z, sum, mx = -1e15, mn = 1e15, flg, flg1, flg2, id1, id2,
                               id3, id4, lim;
char str[1000001], patt[1000001], str1[1000001];
long long failure[1000001], failure2[1000001];
void buildFailure1() {
  failure[0] = failure[1] = 0;
  long long j;
  for (long long i = 2; i <= l; i++) {
    j = failure[i - 1];
    while (true) {
      if (str[j] == str[i - 1]) {
        failure[i] = j + 1;
        break;
      }
      if (j == 0) {
        failure[i] = 0;
        break;
      }
      j = failure[j];
    }
  }
}
void buildFailure2() {
  failure2[0] = failure2[1] = 0;
  long long j;
  for (long long i = 2; i <= l; i++) {
    j = failure2[i - 1];
    while (true) {
      if (patt[j] == patt[i - 1]) {
        failure2[i] = j + 1;
        break;
      }
      if (j == 0) {
        failure2[i] = 0;
        break;
      }
      j = failure2[j];
    }
  }
}
void kmp() {
  l = strlen(str);
  id3 = l - 1;
  for (long long i = 0; i < l; i++) {
    patt[i] = str[id3--];
  }
  patt[l] = '\0';
  buildFailure1();
  buildFailure2();
  d1 = 0;
  mx = 0;
  for (long long i = 0; i < l; i++) {
    if (str[d1] == patt[i]) {
      d1++;
    } else {
      if (d1 == 0) {
        continue;
      }
      d1 = failure[d1];
      i--;
    }
  }
  mx = d1;
  d1 = 0;
  for (long long i = 0; i < l; i++) {
    if (str[i] == patt[d1]) {
      d1++;
    } else {
      if (d1 == 0) {
        continue;
      }
      d1 = failure2[d1];
      i--;
    }
  }
  if (d1 < mx) {
    for (long long i = 0; i < id1; i++) printf("%c", str1[i]);
    for (long long i = 0; i < mx; i++) printf("%c", str[i]);
    for (long long i = id2 + 1; i < lim; i++) printf("%c", str1[i]);
    printf("\n");
  } else {
    for (long long i = 0; i < id1; i++) printf("%c", str1[i]);
    for (long long i = 0; i < d1; i++) printf("%c", patt[i]);
    for (long long i = id2 + 1; i < lim; i++) printf("%c", str1[i]);
    printf("\n");
  }
}
void solve() {
  lim = strlen(str1);
  id1 = 0;
  id2 = lim - 1;
  for (; id1 <= id2;) {
    if (str1[id1] == str1[id2]) {
      id1++;
      id2--;
    } else {
      break;
    }
  }
  if (id1 > id2) {
    for (long long i = 0; i < lim; i++) printf("%c", str1[i]);
    printf("\n");
    return;
  }
  if (id1) {
    id3 = 0;
    for (long long i = id1; i <= id2; i++, id3++) {
      str[id3] = str1[i];
    }
    str[id3] = '\0';
  } else {
    for (long long i = 0, j = lim - 1; i < lim; i++, j--) {
      str[j] = str1[i];
    }
    str[lim] = '\0';
  }
  kmp();
}
int main() {
  scanf("%I64d", &t);
  while (t--) {
    scanf("%s", str1);
    solve();
  }
  return 0;
}
