#include <bits/stdc++.h>
using namespace std;
inline long long gcd(long long a, long long b) {
  while (b != 0) {
    long long c = a % b;
    a = b;
    b = c;
  }
  return a < 0 ? -a : a;
}
inline long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
inline long long lowbit(long long x) { return x & (-x); }
const double PI = 3.14159265358979323846;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const long long mod = 998244353;
inline char nc() {
  static char buf[1 << 21], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long rd() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
const double eps = 1e-8;
const int M = 1e5 + 10;
const int N = 1e6 + 10;
char s[N];
unsigned long long p[N] = {1};
unsigned long long f1[N], f2[N];
unsigned long long gethash1(int l, int r) {
  if (l > r) return 0;
  return (f1[r] % mod - f1[l - 1] * p[r - l + 1] % mod + mod) % mod;
}
unsigned long long gethash2(int l, int r) {
  if (l > r) return 0;
  return (f2[l] % mod - f2[r + 1] * p[r - l + 1] % mod + mod) % mod;
}
bool check1(int st, int ed) {
  int p1, p2;
  if ((ed - st + 1) & 1)
    p1 = (st + ed) / 2 - 1, p2 = p1 + 2;
  else
    p1 = (st + ed) / 2, p2 = p1 + 1;
  return gethash1(st, p1) == gethash2(p2, ed);
}
int main() {
  int t = rd();
  for (int i = 1; i <= 1e6; i++) p[i] = p[i - 1] * 131 % mod;
  while (t--) {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    f2[n + 1] = 0;
    for (int i = 1, j = n; i <= n; j--, i++) {
      f1[i] = (f1[i - 1] * 131 + s[i] - 'a' + 1) % mod;
      f2[j] = (f2[j + 1] * 131 + s[j] - 'a' + 1) % mod;
    }
    string ans = "";
    ans += s[1];
    for (int i = n; i >= 2; i--) {
      if (check1(1, i) && i > ans.size()) {
        ans = "";
        for (int j = 1; j <= i; j++) ans += s[j];
        break;
      }
    }
    for (int i = 1; i < n; i++) {
      if (check1(i, n) && n - i + 1 > ans.size()) {
        ans = "";
        for (int j = i; j <= n; j++) ans += s[j];
        break;
      }
    }
    int len = 0;
    string be = "", to = "";
    for (int i = 1, j = n; i <= n >> 1, j >= 1; i++, j--) {
      if (s[i] != s[j]) break;
      be += s[i];
      len++;
    }
    for (int i = be.length() - 1; i >= 0; i--) to += be[i];
    int st = len + 1, ed = n - len;
    for (int i = ed; i >= st; i--) {
      if (check1(st, i) && len * 2 + i - st + 1 > ans.size()) {
        ans = be;
        for (int j = st; j <= i; j++) ans += s[j];
        ans += to;
        break;
      }
    }
    for (int i = st; i <= ed; i++) {
      if (check1(i, ed) && len * 2 + ed - i + 1 > ans.size()) {
        ans = be;
        for (int j = i; j <= ed; j++) ans += s[j];
        ans += to;
        break;
      }
    }
    cout << ans << endl;
  }
}
