#include <bits/stdc++.h>
using namespace std;
const long long int inf = 1e9 + 7;
const long long int modc = 998244353;
void solve();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}
void solve() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    string a = "", b = "", t = "";
    int left = 0;
    int right = s.size() - 1;
    while (left <= right && s[left] == s[right]) {
      left++;
      right--;
    }
    if (left > right) {
      cout << s << endl;
      continue;
    }
    for (int i = 0; i < left; i++) {
      a += s[i];
    }
    for (int i = right + 1; i < s.size(); i++) {
      b += s[i];
    }
    string m = "";
    for (int i = left; i <= right; i++) {
      m += s[i];
    }
    vector<vector<bool> > dp(m.size(), vector<bool>(m.size(), false));
    for (int i = 0; i < m.size(); i++) {
      dp[i][i] = true;
    }
    for (int i = 0; i < m.size() - 1; i++) {
      if (m[i] == m[i + 1]) {
        dp[i][i + 1] = true;
      }
    }
    for (int len = 3; len <= m.size(); len++) {
      for (int i = 0; i + len - 1 <= m.size() - 1; i++) {
        int j = i + len - 1;
        if (dp[i + 1][j - 1] && m[i] == m[j]) {
          dp[i][j] = true;
        }
      }
    }
    int start1 = 0, end1;
    int maxlen1 = -1;
    for (int i = m.size() - 1; i >= 0; i--) {
      if (dp[start1][i]) {
        maxlen1 = i - start1 + 1;
        end1 = i;
        break;
      }
    }
    start1 += a.size();
    end1 += a.size();
    int start2 = m.size() - 1, end2;
    int maxlen2 = -1;
    for (int i = 0; i < m.size(); i++) {
      if (dp[i][start2]) {
        maxlen2 = start2 - i + 1;
        end2 = i;
        break;
      }
    }
    start2 += a.size();
    end2 += a.size();
    string ans = "";
    if (maxlen1 >= maxlen2) {
      ans += a;
      for (int i = start1; i <= end1; i++) {
        ans += s[i];
      }
      ans += b;
    } else {
      ans += a;
      for (int i = end2; i <= start2; i++) {
        ans += s[i];
      }
      ans += b;
    }
    cout << ans << endl;
  }
}
