#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
using namespace std;
const long long mod = 998244353;
const int inf = 1e9;
int sz(int l, int r) { return r + 1 - l; }
const int N = 1e6 + 10;
const long long base = 41, base2 = 29;
long long hashFromLeft[N], hashFromRight[N];
long long hashFromLeft2[N], hashFromRight2[N];
long long bpow[N], bpow2[N];
string s;
int n;
long long sub(long long a, long long b) { return (a + mod - b) % mod; }
long long mul(long long a, long long b) {
  return ((a % mod) * (b % mod)) % mod;
}
long long hl(long long tbl[], long long bpow[], int i, int j) {
  if (i == 0) return tbl[j];
  long long cax = mul(tbl[i - 1], bpow[j - i + 1]);
  return sub(tbl[j], cax);
}
long long hr(long long tbl[], long long bpow[], int i, int j) {
  if (j == n - 1) return tbl[i];
  long long cax = mul(tbl[j + 1], bpow[j - i + 1]);
  return sub(tbl[i], cax);
}
bool palin(int l, int r) {
  if (l == r) return true;
  if (l > r) return false;
  long long cax = hl(hashFromLeft, bpow, l, r);
  long long loz = hr(hashFromRight, bpow, l, r);
  if (cax != loz) return false;
  cax = hl(hashFromLeft2, bpow2, l, r);
  loz = hr(hashFromRight2, bpow2, l, r);
  return cax == loz;
}
string concua(int l, int r) {
  if (l > r) return string("");
  if (l == r) return string("") + s[l];
  if (s[l] == s[r]) {
    string tmp = concua(l + 1, r - 1);
    return string("") + s[l] + tmp + s[r];
  }
  int k = 1, len = 1;
  for (int i = l + 1; i <= r; ++i)
    if (palin(l, i) && i - l + 1 > len) {
      len = i - l + 1;
      k = len;
    }
  for (int i = r - 1; i >= l; --i)
    if (palin(i, r) && r - i + 1 > len) {
      len = r - i + 1;
      k = -len;
    }
  string ans("");
  if (k > 0) {
    for (int i = l; i <= l + len - 1; ++i) ans += s[i];
  } else {
    for (int i = r - len + 1; i <= r; ++i) ans += s[i];
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  bpow[0] = 1LL;
  for (int i = 1; i < N; ++i) bpow[i] = (bpow[i - 1] * base) % mod;
  bpow2[0] = 1LL;
  for (int i = 1; i < N; ++i) bpow2[i] = (bpow2[i - 1] * base2) % mod;
  while (t--) {
    cin >> s;
    n = s.length();
    hashFromLeft[0] = hashFromLeft2[0] = s[0] - 'a' + 1;
    for (int i = 1; i < n; ++i) {
      hashFromLeft[i] = (hashFromLeft[i - 1] * base + (s[i] - 'a' + 1)) % mod;
      hashFromLeft2[i] =
          (hashFromLeft2[i - 1] * base2 + (s[i] - 'a' + 1)) % mod;
    }
    hashFromRight[n] = hashFromRight2[n] = 0LL;
    for (int i = n - 1; i >= 0; --i) {
      hashFromRight[i] = (hashFromRight[i + 1] * base + (s[i] - 'a' + 1)) % mod;
      hashFromRight2[i] =
          (hashFromRight2[i + 1] * base2 + (s[i] - 'a' + 1)) % mod;
    }
    int l = 0, r = n - 1;
    while (l + 1 < r && s[l] == s[r]) {
      l++;
      r--;
    }
    string ans("");
    for (int i = 0; i < l; ++i) ans += s[i];
    string tmp = concua(l, r);
    ans += tmp;
    for (int i = r + 1; i < n; ++i) ans += s[i];
    cout << ans << '\n';
  }
}
