#include <bits/stdc++.h>
using namespace std;
int num[2000010], f[2000010], t, n;
char s[1000010];
bool bo[1000010];
inline int rd() {
  int x = 0;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    ;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  return x;
}
inline void gao(int n) {
  int mx = 1, id = 1;
  f[1] = 1;
  for (int i = 2; i < n; i++) {
    f[i] = (i > mx) ? 1 : min(mx - i + 1, f[id * 2 - i]);
    while (num[i - f[i]] == num[i + f[i]]) f[i]++;
    if (f[i] > mx) mx = f[i], id = i;
  }
}
inline void work() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  bo[0] = true;
  for (int i = 1; i <= n; i++) bo[i] = bo[i - 1] && (s[i] == s[n - i + 1]);
  num[0] = -233;
  for (int i = 1; i <= n; i++) num[i * 2 - 1] = -1, num[i * 2] = s[i] - 'a';
  num[n * 2 + 1] = -1;
  num[n * 2 + 2] = -2333;
  gao(n * 2 + 2);
  int ans = 0, id = 0;
  for (int i = 1; i <= n; i++) {
    int hh = f[i * 2] / 2;
    int l = i - hh + 1, r = i + hh - 1;
    if (l - 1 <= n - r) {
      if (bo[l - 1]) {
        if ((l - 1) * 2 + hh * 2 - 1 > ans)
          ans = (l - 1) * 2 + hh * 2 - 1, id = i * 2;
      }
    } else {
      if (bo[n - r]) {
        if ((n - r) * 2 + hh * 2 - 1 > ans)
          ans = (n - r) * 2 + hh * 2 - 1, id = i * 2;
      }
    }
  }
  for (int i = 1; i < n; i++) {
    int hh = f[i * 2 + 1] / 2;
    int l = i - hh + 1, r = i + hh;
    if (l - 1 <= n - r) {
      if (bo[l - 1]) {
        if ((l - 1) * 2 + hh * 2 > ans)
          ans = (l - 1) * 2 + hh * 2, id = i * 2 + 1;
      }
    } else {
      if (bo[n - r]) {
        if ((n - r) * 2 + hh * 2 > ans)
          ans = (n - r) * 2 + hh * 2, id = i * 2 + 1;
      }
    }
  }
  if (id % 2 == 0) {
    int i = id / 2;
    int hh = f[i * 2] / 2;
    int l = i - hh + 1, r = i + hh - 1;
    if (l - 1 <= n - r) {
      for (int i = 1; i <= l - 1; i++) putchar(s[i]);
      for (int i = l; i <= r; i++) putchar(s[i]);
      for (int i = n - (l - 1) + 1; i <= n; i++) putchar(s[i]);
      putchar('\n');
    } else {
      for (int i = 1; i <= n - r; i++) putchar(s[i]);
      for (int i = l; i <= r; i++) putchar(s[i]);
      for (int i = n - (n - r) + 1; i <= n; i++) putchar(s[i]);
      putchar('\n');
    }
  } else {
    int i = id / 2;
    int hh = f[i * 2 + 1] / 2;
    int l = i - hh + 1, r = i + hh;
    if (l - 1 <= n - r) {
      for (int i = 1; i <= l - 1; i++) putchar(s[i]);
      for (int i = l; i <= r; i++) putchar(s[i]);
      for (int i = n - (l - 1) + 1; i <= n; i++) putchar(s[i]);
      putchar('\n');
    } else {
      for (int i = 1; i <= n - r; i++) putchar(s[i]);
      for (int i = l; i <= r; i++) putchar(s[i]);
      for (int i = n - (n - r) + 1; i <= n; i++) putchar(s[i]);
      putchar('\n');
    }
  }
}
int main() {
  t = rd();
  while (t--) work();
  return 0;
}
