#include <bits/stdc++.h>
using namespace std;
long long t, n;
string s;
long long b[5050][5050];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> t;
  while (t--) {
    cin >> s;
    n = s.length();
    for (long long i = (n - 1); i >= 0; i--)
      for (long long j = 0; j < n; j++) {
        if (i >= j)
          b[i][j] = 1;
        else if ((b[i + 1][j - 1] == 1) && (s[i] == s[j]))
          b[i][j] = 1;
        else
          b[i][j] = 0;
      }
    long long ki = 0, ka = n - 1;
    string kiri = "";
    string kanan = "";
    string tengah = "";
    while ((ki < ka) && (s[ki] == s[ka])) {
      kiri += s[ki];
      kanan += s[ka];
      ki++;
      ka--;
    }
    reverse(kanan.begin(), kanan.end());
    long long h1 = 0, h2 = 0;
    for (long long i = ki; i < ka; i++)
      if (b[ki][i]) h1 = i - ki + 1;
    for (long long i = ka; i > ki; i--)
      if (b[i][ka]) h2 = ka - i + 1;
    if (ki == ka) h1 = 1;
    if (h1 > h2) {
      for (long long i = ki; i < (ki + h1); i++) tengah += s[i];
    } else {
      for (long long i = ka; i > (ka - h2); i--) tengah += s[i];
    }
    cout << kiri + tengah + kanan << "\n";
  }
}
