#include <bits/stdc++.h>
using namespace std;
char s[1000005];
long long pre[1000005];
long long suf[1000005];
long long pre2[1000005];
long long suf2[1000005];
long long ksm2[1000005];
long long ksm[1000005];
long long p = 1e9 + 9, mod = 19260817, mod2 = 1e9 + 21;
void init() {
  int len = strlen(s + 1);
  ksm[0] = 1;
  pre[0] = 0;
  suf[len + 1] = 0;
  ksm2[0] = 1;
  pre2[0] = 0;
  suf2[len + 1] = 0;
  for (int i = 1; i <= len; i++) {
    pre[i] = (pre[i - 1] * p + s[i]) % mod;
    pre2[i] = (pre2[i - 1] * p + s[i]) % mod2;
    ksm[i] = (ksm[i - 1] * p) % mod;
    ksm2[i] = (ksm2[i - 1] * p) % mod2;
  }
  for (int i = len; i >= 1; i--) {
    suf[i] = (suf[i + 1] * p + s[i]) % mod;
    suf2[i] = (suf2[i + 1] * p + s[i]) % mod2;
  }
}
long long h1(int i, int j) {
  return (mod + pre[j] - (pre[i - 1] * ksm[j - i + 1]) % mod) % mod;
}
long long h2(int i, int j) {
  return (mod + suf[i] - (suf[j + 1] * ksm[j - i + 1]) % mod) % mod;
}
long long h3(int i, int j) {
  return (mod2 + pre2[j] - (pre2[i - 1] * ksm2[j - i + 1]) % mod2) % mod2;
}
long long h4(int i, int j) {
  return (mod2 + suf2[i] - (suf2[j + 1] * ksm2[j - i + 1]) % mod2) % mod2;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%s", s + 1);
    init();
    string anss = "";
    int len = strlen(s + 1);
    int ex = len;
    if (len > 1) {
      for (int i = 1; i <= len / 2; i++) {
        if (s[i] != s[ex]) {
          break;
        }
        ex--;
      }
      for (int i = 1; i <= len - ex; i++) anss += s[i];
    }
    int lc = len - ex + 1, rc = ex;
    string anst1 = "", anst2 = "";
    for (int i = len; i >= lc; i--) {
      int le = (i - lc);
      if (i + le + 1 <= rc) {
        if (h1(lc, i) == h2(i + 1, i + le + 1) &&
            h3(lc, i) == h4(i + 1, i + le + 1)) {
          for (int j = lc; j <= i; j++) anst1 += s[j];
          for (int j = i; j >= lc; j--) anst1 += s[j];
          break;
        }
      }
      if (i + le <= rc) {
        if (h1(lc, i - 1) == h2(i + 1, i + le) &&
            h3(lc, i - 1) == h4(i + 1, i + le)) {
          for (int j = lc; j <= i - 1; j++) anst1 += s[j];
          anst1 += s[i];
          for (int j = i - 1; j >= lc; j--) anst1 += s[j];
          break;
        }
      }
    }
    for (int i = 1; i <= rc; i++) {
      int le = (rc - i);
      if (i - le - 1 >= lc) {
        if (h1(i - le - 1, i - 1) == h2(i, i + le) &&
            h3(i - le - 1, i - 1) == h4(i, i + le)) {
          for (int j = i - le - 1; j <= i - 1; j++) anst2 += s[j];
          for (int j = i - 1; j >= i - le - 1; j--) anst2 += s[j];
          break;
        }
      }
      if (i - le >= lc) {
        if (h1(i - le, i - 1) == h2(i + 1, rc) &&
            h3(i - le, i - 1) == h4(i + 1, rc)) {
          for (int j = i - le; j <= i - 1; j++) anst2 += s[j];
          anst2 += s[i];
          for (int j = i - 1; j >= i - le; j--) anst2 += s[j];
          break;
        }
      }
    }
    if (anst1.length() >= anst2.length()) {
      anss += anst1;
    } else {
      anss += anst2;
    }
    for (int i = len - ex; i >= 1; i--) anss += s[i];
    for (int i = 0; i < anss.length(); i++) printf("%c", anss[i]);
    printf("\n");
  }
  return 0;
}
