#include <bits/stdc++.h>
using namespace std;
int Z[10000000];
bool doixung(int l, int r, string s) {
  while (l < r && l < s.size() && r >= 0) {
    if (s[l] != s[r]) return false;
    l++;
    r--;
  }
  return true;
}
void Z_function(string s) {
  int n = s.size();
  int R, L;
  L = R = 0;
  Z[0] = n;
  for (int i = 1; i < n; i++) {
    if (i > R) {
      L = R = i;
      while (R < n && s[R] == s[R - L]) R++;
      Z[i] = R - L;
      R--;
    } else {
      if (Z[i - L] < (R - i + 1))
        Z[i] = Z[i - L];
      else {
        L = i;
        while (R < n && s[R] == s[R - L]) R++;
        Z[i] = R - L;
        R--;
      }
    }
  }
}
void go() {
  string s, frex, suff;
  cin >> s;
  string s1, tmp = s;
  s1 = s;
  reverse(tmp.begin(), tmp.end());
  s1 += '!' + tmp;
  Z_function(s1);
  if (Z[s.size() + 1] >= s.size() / 2) {
    cout << s << endl;
    return;
  }
  for (int i = 0; i < Z[s.size() + 1]; i++) {
    frex += s[i];
    suff = s[i] + suff;
  }
  int lf = Z[s.size() + 1], ad1 = 0, ad2 = 0;
  int rg = s.size() - Z[s.size() + 1] - 1;
  for (int i = lf; i <= rg; i++) {
    if (doixung(lf, i, s)) {
      ad1 = i - lf;
    }
    if (doixung(i, rg, s)) {
      ad2 = max(rg - i, ad2);
    }
  }
  if (ad1 > ad2) {
    for (int i = lf; i <= lf + ad1; i++) frex += s[i];
  } else {
    for (int i = rg - ad2; i <= rg; i++) frex += s[i];
  }
  cout << frex << suff << endl;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    go();
  }
  return 0;
}
