#include <bits/stdc++.h>
using namespace std;
template <class T>
void print(const T niz[], const int siz) {
  for (int i = 0; i < siz; i++) cout << niz[i] << " ";
  cout << endl;
}
const long long p = 103;
long long add(long long x, long long y) { return (x + y) % 1000000007; }
long long mul(long long x, long long y) { return (x * y) % 1000000007; }
long long power(long long x, long long y) {
  if (y == 0) return 1;
  long long pola = power(x, y / 2);
  pola = mul(pola, pola);
  if (y % 2 == 1) pola = mul(pola, x);
  return pola;
}
long long inverz[1000005];
int n;
string x;
long long hes[1000005][2];
long long get(long long l, long long r, long long idx) {
  if (idx == 0) {
    long long sta = hes[r][0] - hes[l - 1][0];
    sta %= 1000000007;
    sta += 1000000007;
    sta %= 1000000007;
    sta = mul(sta, inverz[l - 1]);
    return sta;
  } else {
    long long sta = hes[l][1] - hes[r + 1][1];
    sta %= 1000000007;
    sta += 1000000007;
    sta %= 1000000007;
    sta = mul(sta, inverz[n - r]);
    return sta;
  }
}
bool checkpal(int l, int r) {
  l = max(l, 0);
  r = min(r, n);
  if (l == r) return 1;
  if (l > r) return 0;
  long long sta1 = get(l, r, 0);
  long long sta2 = get(l, r, 1);
  return (sta1 == sta2);
}
int maksn = 0;
void solve() {
  cin >> x;
  n = x.length();
  maksn = max(maksn, n);
  for (int(i) = (0); (i) <= (maksn + 1); ++(i)) {
    hes[i][0] = hes[i][1] = 0;
  }
  long long st = 1;
  long long tr = 0;
  for (int(i) = (0); (i) <= (n - 1); ++(i)) {
    tr = add(tr, mul(st, x[i] - 'a' + 1));
    hes[i + 1][0] = tr;
    st = mul(st, p);
  }
  tr = 0;
  st = 1;
  for (int(i) = (n - 1); (i) >= (0); --(i)) {
    tr = add(tr, mul(st, x[i] - 'a' + 1));
    hes[i + 1][1] = tr;
    st = mul(st, p);
  }
  int l = 1;
  int r = n;
  if (checkpal(1, n)) {
    cout << x << endl;
    return;
  }
  int necul = 0;
  int necur = 0;
  while (l < r) {
    if (x[l - 1] != x[r - 1]) {
      for (int(i) = (l); (i) <= (r); ++(i)) {
        if (checkpal(l, i)) {
          necul = i + 1;
          necur = r;
        }
      }
      for (int(i) = (r); (i) >= (l); --(i)) {
        if (checkpal(i, r)) {
          if ((i - 1 - l) < (necur - necul)) {
            necur = i - 1;
            necul = l;
          }
        }
      }
      break;
    } else {
      l++;
      r--;
    }
  }
  for (int(i) = (1); (i) <= (n); ++(i)) {
    if (i >= necul && i <= necur) continue;
    cout << x[i - 1];
  }
  cout << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  inverz[1000001] = power(power(p, 1000001), 1000000007 - 2);
  for (int(i) = (1000000); (i) >= (0); --(i)) inverz[i] = mul(inverz[i + 1], p);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
