#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5010;
const int MAX_M = 201;
const long long INF = 1000000000000000000;
const long long P = 998244353;
const int SIGMA = 28;
int start[MAX_N], endh[MAX_N];
void clear(int n) {
  for (int i = 0; i < n; i++) {
    start[i] = endh[i] = i;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    string str;
    cin >> str;
    if ((int)str.size() == 1) {
      cout << str << "\n";
      continue;
    }
    if ((int)str.size() == 2) {
      if (str[0] != str[1])
        cout << str[0] << "\n";
      else
        cout << str << "\n";
      continue;
    }
    clear((int)str.size());
    for (int i = 0; i < (int)str.size(); i++) {
      for (int j = i, k = i; 0 <= j && k < (int)str.size(); j--, k++) {
        if (str[j] != str[k]) break;
        if ((int)str.size() - (k + 1) - 1 < j) {
          endh[k] = min(endh[k], j);
        }
        if (k < (int)str.size() - (j + 1)) {
          start[j] = max(start[j], k);
        }
      }
      for (int j = i, k = i + 1; 0 <= j && k < (int)str.size(); j--, k++) {
        if (str[j] != str[k]) break;
        if ((int)str.size() - (k + 1) - 1 < j) {
          endh[k] = min(endh[k], j);
        }
        if (k < (int)str.size() - (j + 1)) {
          start[j] = max(start[j], k);
        }
      }
    }
    pair<int, pair<int, int> > p =
        pair<int, pair<int, int> >(0, pair<int, int>(0, 0));
    for (int i = 1, j = (int)str.size() - 2; i < j; i++, j--) {
      if (str[i - 1] != str[j + 1]) break;
      int mi = start[i], mj = endh[j];
      if (mj < i) continue;
      if (mi > j) continue;
      pair<int, pair<int, int> > pi = pair<int, pair<int, int> >(
          mi - i + 1 + i * 2, pair<int, int>(mi, j + 1));
      pair<int, pair<int, int> > pj = pair<int, pair<int, int> >(
          (mj == -1) ? -1 : (j - mj + 1 + i * 2), pair<int, int>(i - 1, mj));
      p = max(p, max(pi, pj));
    }
    int beg = start[0];
    int end = endh[(int)str.size() - 1];
    if (beg + 1 > (int)str.size() - end) {
      if (beg + 1 > p.first) {
        cout << str.substr(0, beg + 1) << "\n";
      } else {
        pair<int, int> b = p.second;
        cout << str.substr(0, b.first + 1) +
                    str.substr(b.second, (int)str.size() - b.second)
             << "\n";
      }
    } else if ((int)str.size() - end > p.first) {
      cout << str.substr(end, (int)str.size() - end) << "\n";
    } else {
      pair<int, int> b = p.second;
      cout << str.substr(0, b.first + 1) +
                  str.substr(b.second, (int)str.size() - b.second)
           << "\n";
    }
  }
  return 0;
}
