#include <bits/stdc++.h>
using namespace std;
int n, m, cas, p[1000005 << 1];
char rS[1000005], S[1000005], T[1000005 << 1];
bool f[1000005];
inline void Build(char S[], char T[]) {
  m = strlen(S + 1);
  for (int i = 1; i <= m; i++) rS[i] = S[m - i + 1];
  T[0] = '$';
  T[1] = '#';
  for (int i = 1; i <= m; i++) T[i << 1] = S[i], T[i << 1 | 1] = '#';
  T[(m + 1) << 1] = '\0';
  return;
}
inline void Manacher(char S[]) {
  n = strlen(S + 1);
  int mx = 0, id = 0;
  assert(n == (m << 1 | 1));
  for (int i = 0; i <= n + 5; i++) p[i] = 0;
  for (int i = 1; i <= n; i++) {
    if (mx > i)
      p[i] = min(p[(id << 1) - i], mx - i);
    else
      p[i] = 1;
    while (S[i + p[i]] == S[i - p[i]]) ++p[i];
    if (mx < i + p[i]) mx = i + p[i], id = i;
  }
  return;
}
int main() {
  scanf("%d", &cas);
  while (cas--) {
    scanf("%s", S + 1);
    Build(S, T);
    Manacher(T);
    memset(f, 0, m + 5);
    f[0] = true;
    for (int i = 1; i <= m; i++) {
      f[i] = (S[i] == rS[i]);
      if (!f[i]) break;
    }
    int ans = 0, id = 0;
    for (int i = 1; i <= n; i++) {
      int t;
      --p[i];
      if (i <= m) {
        t = (i - p[i]) >> 1;
        if (f[t] && t * 2 + p[i] > ans) ans = t * 2 + p[i], id = i;
      } else {
        t = m - ((i + p[i]) >> 1);
        if (f[t] && t * 2 + p[i] > ans) ans = t * 2 + p[i], id = i;
      }
    }
    if (id <= m) {
      for (int i = 1; i <= id + p[id]; i++)
        if (T[i] != '#') putchar(T[i]);
      int q = id - p[id];
      for (int i = n - q + 1; i < n; i++)
        if (T[i] != '#') putchar(T[i]);
    } else {
      int q = n - id - p[id];
      for (int i = 1; i <= q; i++)
        if (T[i] != '#') putchar(T[i]);
      for (int i = id - p[id] + 1; i < n; i++)
        if (T[i] != '#') putchar(T[i]);
    }
    putchar('\n');
  }
  return 0;
}
