#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000003;
char s[maxn], t[maxn], tt[maxn];
int kmp[maxn];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", s + 1);
    int n = strlen(s + 1), p, len = 0;
    for (p = 1; p <= n / 2 && s[p] == s[n - p + 1]; p++)
      ;
    if (p > n / 2) {
      puts(s + 1);
      continue;
    }
    for (int i = p; i <= n - p + 1; i++) t[++len] = s[i];
    for (int i = 1; i <= len; i++) t[i + len] = t[i];
    reverse(t + len + 1, t + len * 2 + 1);
    len *= 2;
    int pos = 0;
    for (int i = 2; i <= len; i++) {
      while (pos && t[pos + 1] != t[i]) pos = kmp[pos];
      if (t[pos + 1] == t[i]) pos++;
      kmp[i] = pos;
    }
    int tmp = kmp[len];
    while (tmp > len / 2) tmp = kmp[tmp];
    int ANS1 = (p - 1) * 2 + tmp;
    for (int i = 1; i <= len; i++) tt[i] = t[i], kmp[i] = 0;
    len = 0;
    for (int i = n - p + 1; i >= p; i--) t[++len] = s[i];
    for (int i = 1; i <= len; i++) t[i + len] = t[i];
    reverse(t + len + 1, t + len * 2 + 1);
    len *= 2;
    pos = 0;
    for (int i = 2; i <= len; i++) {
      while (pos && t[pos + 1] != t[i]) pos = kmp[pos];
      if (t[pos + 1] == t[i]) pos++;
      kmp[i] = pos;
    }
    tmp = kmp[len];
    while (tmp > len / 2) tmp = kmp[tmp];
    int ANS2 = (p - 1) * 2 + tmp;
    for (int i = 1; i <= len; i++) kmp[i] = 0;
    for (int i = 1; i < p; i++) putchar(s[i]);
    if (ANS1 > ANS2)
      for (int i = 1; i <= ANS1 - (p - 1) * 2; i++) putchar(tt[i]);
    else
      for (int i = 1; i <= ANS2 - (p - 1) * 2; i++) putchar(t[i]);
    for (int i = p - 1; i >= 1; i--) putchar(s[i]);
    putchar('\n');
  }
  return 0;
}
