#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
template <typename T = int>
inline const T read() {
  T 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 - '0';
    ch = getchar();
  }
  return x * f;
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
const int maxn = 1e6 + 10;
const unsigned long long p = 13331, mod = 19260817;
unsigned long long pwr[maxn], pre[maxn], suf[maxn];
char s[maxn];
unsigned long long hash_suf(int a, int b) {
  return (suf[a] - pwr[b - a + 1] * suf[b + 1] % mod + mod) % mod;
}
unsigned long long hash_pre(int a, int b) {
  return (pre[b] - pwr[b - a + 1] * pre[a - 1] % mod + mod) % mod;
}
void func1(int n) {
  for (int i = n; i >= 1; i--)
    suf[i] = (suf[i + 1] * p + (s[i] + 1 - 'a')) % mod;
}
void func2(int n) {
  for (int i = 1; i <= n; i++)
    pre[i] = (pre[i - 1] * p + (s[i] + 1 - 'a')) % mod;
}
int main() {
  int t = read();
  pwr[0] = 1;
  for (int i = 1; i < maxn; i++) pwr[i] = pwr[i - 1] * p % mod;
  while (t--) {
    scanf("%s", s + 1);
    int n = (int)strlen(s + 1);
    pre[0] = suf[n + 1] = 0;
    func1(n);
    func2(n);
    int m = 0, se = 0;
    bool flag = false;
    while (s[m + 1] == s[n - m] && m + 1 < n - m) m++;
    for (int i = m + 1; i <= n - m; i++) {
      if (hash_suf(m + 1, i) == hash_pre(m + 1, i) && i - m > se) {
        flag = false;
        se = i - m;
      }
    }
    for (int i = n - m; i >= m + 1; i--) {
      if (hash_suf(i, n - m) == hash_pre(i, n - m) && n - m + 1 - i > se) {
        se = n - i - m + 1;
        flag = true;
      }
    }
    for (int i = 1; i <= m; i++) cout << s[i];
    if (flag)
      for (int i = n - m; i >= n - m - se + 1; i--) cout << s[i];
    else
      for (int i = m + 1; i <= m + se; i++) cout << s[i];
    for (int i = n - m + 1; i <= n; i++) cout << s[i];
    cout << endl;
  }
  return 0;
}
