#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
long long mod[4] = {19260817, 19260817, 19260817, 19260817};
long long o = 1e9 + 7;
char s[maxn];
int T, n, k, kk;
long long pre[maxn][4], suf[maxn][4], p[maxn][4];
long long h1(int l, int r, int x) {
  return (pre[r][x] - pre[l - 1][x] * p[r - l + 1][x] % o + o) % o;
}
long long h2(int l, int r, int x) {
  return (suf[l][x] - suf[r + 1][x] * p[r - l + 1][x] % o + o) % o;
}
bool check(int l, int r) {
  for (int i = 0; i <= 3; ++i)
    if (h1(l, r, i) != h2(l, r, i)) return false;
  return true;
}
int main() {
  cin >> T;
  p[0][0] = p[0][1] = p[0][2] = p[0][3] = 1;
  for (int j = 0; j <= 3; ++j)
    for (int i = 1; i <= 1e6; ++i) p[i][j] = p[i - 1][j] * mod[j] % o;
  while (T--) {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    int l = 1, r = n;
    for (int i = 0; i <= 3; ++i) suf[n + 1][i] = 0, pre[0][i] = 0;
    while (s[l] == s[r] && l < r) l++, r--;
    if (l >= r) {
      for (int i = 1; i <= n; ++i) cout << s[i];
      cout << '\n';
      continue;
    }
    for (int j = 0; j <= 3; ++j)
      for (int i = 1; i <= n; ++i)
        pre[i][j] = (pre[i - 1][j] * mod[j] % o + (unsigned long long)s[i]) % o;
    for (int j = 0; j <= 3; ++j)
      for (int i = n; i >= 1; --i)
        suf[i][j] = (suf[i + 1][j] * mod[j] % o + (unsigned long long)s[i]) % o;
    for (int i = r; i >= l; --i)
      if (check(l, i)) {
        k = i;
        break;
      }
    for (int i = l; i <= r; ++i)
      if (check(i, r)) {
        kk = i;
        break;
      }
    int x = k - l, y = r - kk;
    if (x > y) {
      for (int i = 1; i <= l - 1; ++i) cout << s[i];
      for (int i = l; i <= k; ++i) cout << s[i];
      for (int i = r + 1; i <= n; ++i) cout << s[i];
      cout << '\n';
    } else {
      for (int i = 1; i <= l - 1; ++i) cout << s[i];
      for (int i = kk; i <= r; ++i) cout << s[i];
      for (int i = r + 1; i <= n; ++i) cout << s[i];
      cout << '\n';
    }
  }
  return 0;
}
