#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;
const int INFMEM = 63;
const int INF = 1061109567;
const long long LINF = 4557430888798830399LL;
const double DINF = numeric_limits<double>::infinity();
const long long MOD = 1000000007;
const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
const double PI = 3.141592653589793;
inline void open(string a) {
  freopen((a + ".in").c_str(), "r", stdin);
  freopen((a + ".out").c_str(), "w", stdout);
}
inline void fasterios() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
string s;
int maxlen;
struct dt {
  int kiri, kanan;
  bool dariKiri;
} posAns;
int memo[5005][5005];
int dp(int kiri, int kanan) {
  if (kiri >= kanan) return 1;
  int &ret = memo[kiri][kanan];
  if (ret != -1) return ret;
  return ret = (s[kiri] == s[kanan] ? dp(kiri + 1, kanan - 1) : 0);
}
int main() {
  fasterios();
  long long t;
  cin >> t;
  while (t--) {
    cin >> s;
    maxlen = 0;
    int n = s.length();
    for (int i = 0; i <= n + 1; i++) {
      for (int j = 0; j <= n + 1; j++) {
        memo[i][j] = -1;
      }
    }
    if (dp(0, n - 1)) {
      cout << s << '\n';
      continue;
    }
    posAns = {-1, n, 0};
    int curLen = 0;
    for (int kiri = -1, kanan = n; kiri <= kanan; kiri++, kanan--) {
      for (int i = kanan - 1; i >= kiri + 1; i--) {
        if (dp(kiri + 1, i)) {
          int curcount = curLen + (i - kiri);
          if (curcount > maxlen) {
            maxlen = curcount;
            posAns = {kiri, kanan, 0};
          }
          break;
        }
      }
      for (int i = kiri + 1; i <= kanan - 1; i++) {
        if (dp(i, kanan - 1)) {
          int curcount = curLen + (kanan - i);
          if (curcount > maxlen) {
            maxlen = curcount;
            posAns = {kiri, kanan, 1};
          }
          break;
        }
      }
      if (s[kiri + 1] != s[kanan - 1]) break;
      curLen += 2;
    }
    string ans = "";
    for (int i = 0; i <= posAns.kiri; i++) {
      ans += s[i];
    }
    if (!posAns.dariKiri) {
      for (int i = posAns.kanan - 1; i >= posAns.kiri + 1; i--) {
        if (dp(posAns.kiri + 1, i)) {
          for (int j = posAns.kiri + 1; j <= i; j++) {
            ans += s[j];
          }
          break;
        }
      }
    } else {
      for (int i = posAns.kiri + 1; i <= posAns.kanan - 1; i++) {
        if (dp(i, posAns.kanan - 1)) {
          for (int j = i; j <= posAns.kanan - 1; j++) {
            ans += s[j];
          }
          break;
        }
      }
    }
    for (int i = posAns.kanan; i < n; i++) ans += s[i];
    cout << ans << '\n';
  }
  return 0;
}
