#include <bits/stdc++.h>
using namespace std;
char str[5005];
bool dp[5005][5005];
char ans[5005];
int main() {
  int n, te;
  scanf("%d", &te);
  int arr[5005] = {};
  int maxlen = 0;
  bool flag;
  while (te--) {
    scanf("%s", str);
    n = strlen(str);
    for (int i = 0; i < n; i++) dp[i][i] = true;
    for (int i = n - 1; i >= 0; i--) {
      for (int j = i + 1; j < n; j++) {
        if (str[i] == str[j]) {
          dp[i][j] = dp[i + 1][j - 1] || (j - i == 1);
        }
      }
    }
    int ini, sublen;
    for (int i = 0; i < n; i++)
      if (2 * i < (n - 1)) {
        if (str[i] == str[n - 1 - i]) {
          for (int j = n - 2 - i; j >= i + 1; j--)
            if (dp[i + 1][j]) {
              int len = 2 * (i + 1) + j - i;
              if (maxlen < len) {
                maxlen = len;
                ini = i;
                sublen = j - i;
                flag = true;
              }
            }
          for (int j = i + 1; j <= n - 2 - i; j++)
            if (dp[j][n - 2 - i]) {
              int len = 2 * (i + 1) + (n - 1 - i) - j;
              if (maxlen < len) {
                maxlen = len;
                ini = i;
                sublen = (n - 1 - i) - j;
                flag = false;
              }
            }
        } else
          break;
      }
    int top = -1;
    if (maxlen > 0) {
      for (int i = 0; i <= ini; i++) ans[++top] = str[i];
      if (flag) {
        for (int i = 0; i < sublen; i++) ans[++top] = str[i + ini + 1];
      } else {
        for (int i = sublen - 1; i >= 0; i--) {
          ans[++top] = str[n - ini - 2 - i];
        }
      }
      for (int i = n - ini - 1; i < n; i++) ans[++top] = str[i];
    }
    for (int i = n - 1; i >= 0; i--)
      if (dp[0][i]) {
        if (maxlen < i + 1) {
          maxlen = i + 1;
          for (int j = 0; j <= i; j++) {
            ans[j] = str[j];
          }
        }
        break;
      }
    for (int i = 0; i < n; i++)
      if (dp[i][n - 1]) {
        if (maxlen < n - i) {
          maxlen = n - i;
          for (int j = i; j < n; j++) ans[j - i] = str[j];
        }
        break;
      }
    printf("%s\n", ans);
    for (int i = 0; i < n; i++) ans[i] = 0;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) dp[i][j] = 0;
    maxlen = 0;
  }
}
