#include <bits/stdc++.h>
using namespace std;
string s;
string pref(int st, int end) {
  int n = end - st + 1;
  string kaua = "";
  for (int i = st; i <= end; i++) kaua += s[i];
  bool table[n][n];
  memset(table, false, sizeof(table));
  for (int i = 0; i < n; i++) table[i][i] = true;
  for (int i = 0; i < n - 1; i++) {
    if (kaua[i] == kaua[i + 1]) table[i][i + 1] = true;
  }
  for (int k = 3; k <= n; k++) {
    for (int i = 0; i < n - k + 1; i++) {
      int j = i + k - 1;
      if (table[i + 1][j - 1] && kaua[i] == kaua[j]) table[i][j] = true;
    }
  }
  int len1 = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (table[0][i]) {
      len1 = i + 1;
      break;
    }
  }
  string a = "";
  for (int i = 0; i < len1; i++) a += kaua[i];
  return a;
}
string suff(int st, int end) {
  int n = end - st + 1;
  string kaua = "";
  for (int i = st; i <= end; i++) kaua += s[i];
  bool table[n][n];
  memset(table, false, sizeof(table));
  for (int i = 0; i < n; i++) table[i][i] = true;
  for (int i = 0; i < n - 1; i++) {
    if (kaua[i] == kaua[i + 1]) table[i][i + 1] = true;
  }
  for (int k = 3; k <= n; k++) {
    for (int i = 0; i < n - k + 1; i++) {
      int j = i + k - 1;
      if (table[i + 1][j - 1] && kaua[i] == kaua[j]) table[i][j] = true;
    }
  }
  int len2 = 0;
  for (int i = 0; i < n; i++) {
    if (table[i][n - 1]) {
      len2 = n - i;
      break;
    }
  }
  string b = "";
  for (int i = n - 1; i >= n - len2; i--) {
    b += kaua[i];
  }
  reverse(b.begin(), b.end());
  return b;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    s.clear();
    cin >> s;
    string a = "";
    int n = s.size();
    int st = 0, end = n - 1;
    int i;
    for (i = 0; i < n / 2;) {
      if (s[i] == s[n - i - 1])
        a += s[i], i++;
      else
        break;
    }
    i--;
    if (a.size() == 0) {
      string k = pref(0, n - 1);
      string m = suff(0, n - 1);
      if (m.size() > k.size()) {
        cout << m;
      } else
        cout << k;
      cout << "\n";
    } else {
      st = i + 1, end = n - i - 2;
      string b = a;
      reverse(b.begin(), b.end());
      string mid1 = "";
      string mid2 = "";
      if (st <= end) {
        mid1 = pref(st, end);
        mid2 = suff(st, end);
      }
      string ans1 = a + mid1 + b, ans2 = a + mid2 + b;
      if (ans1.size() > ans2.size())
        cout << ans1 << "\n";
      else
        cout << ans2 << "\n";
    }
  }
}
