#include <bits/stdc++.h>
using namespace std;
int t, n, i, k, j, lg, el, maxi, ok2;
int ok[5010][5010];
char v[5010], sol[5010];
int main() {
  cin >> t;
  for (; t--;) {
    cin >> v + 1;
    n = strlen(v + 1);
    int st = 1, dr = n;
    while (st <= dr && v[st] == v[dr]) st++, dr--;
    if (st > dr) {
      cout << v + 1 << "\n";
      continue;
    }
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++) ok[i][j] = 0;
    for (i = 1; i <= n; ++i) {
      ok[i][i] = 1;
      if (i < n && v[i] == v[i + 1]) ok[i][i + 1] = 1;
    }
    for (lg = 3; lg <= n; ++lg) {
      for (i = 1; i + lg - 1 <= n; ++i) {
        j = i + lg - 1;
        if (ok[i + 1][j - 1] && v[i] == v[j]) ok[i][j] = 1;
      }
    }
    maxi = 0;
    for (i = 1; i <= n; i++) {
      if (ok[1][i] && i > maxi) {
        maxi = i;
        for (j = 1; j <= i; j++) sol[j] = v[j];
      }
      if (ok[i][n] && (n - i + 1) > maxi) {
        maxi = n - i + 1;
        for (j = i; j <= n; j++) sol[j - i + 1] = v[j];
      }
    }
    dr = n;
    for (i = 1; i <= n; i++) {
      st = 1, ok2 = 0;
      for (j = n; j >= n - i + 1 && j > i; j--) {
        if (v[st] != v[j]) {
          ok2 = 1;
          break;
        }
        st++;
      }
      if (j == n) continue;
      if (st != i + 1) {
        int nr = n - j;
        if (2 * nr > maxi) {
          maxi = 2 * nr, el = 0;
          for (j = 1; j <= nr; j++) sol[++el] = v[j];
          for (j = n - nr + 1; j <= n; j++) sol[++el] = v[j];
        }
        if (ok[nr + 1][i]) {
          if (i + nr > maxi) {
            maxi = i + nr, el = 0;
            for (j = 1; j <= i; j++) sol[++el] = v[j];
            for (j = n - nr + 1; j <= n; j++) sol[++el] = v[j];
          }
        }
      } else {
        for (j = i + 1; j <= n - i; j++) {
          if (ok[j][n - i]) break;
        }
        int lg = n - i - j + 1;
        if (2 * i + lg > maxi) {
          maxi = 2 * i + lg, el = 0;
          for (k = 1; k <= i; k++) sol[++el] = v[k];
          for (k = j; k <= n; k++) sol[++el] = v[k];
        }
      }
    }
    for (i = 1; i <= maxi; i++) cout << sol[i];
    cout << "\n";
  }
  return 0;
}
