#include <bits/stdc++.h>
using namespace std;
vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; ++i) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) ++j;
    pi[i] = j;
  }
  return pi;
}
vector<int> count(const string& s) {
  int n = (int)s.length();
  vector<int> cnt(n);
  cnt[0] = 1;
  for (int i = 1; i < n; i++) {
    if (s[i] == s[i - 1])
      cnt[i] = cnt[i - 1] + 1;
    else
      cnt[i] = 1;
  }
  return cnt;
}
int main() {
  int n, k, l, m;
  string s, t, w, torig, trev;
  cin >> n;
  for (int j = 0; j < n; j++) {
    cin >> s;
    k = 0;
    l = s.length();
    while (s[k] == s[l - k - 1] && k < l - k - 1) k++;
    t = s.substr(k, l - 2 * k);
    torig = t;
    trev = t;
    reverse(trev.begin(), trev.end());
    m = 0;
    w = "";
    int tl = t.length();
    auto tmp = prefix_function(torig + "#" + trev);
    if (tmp[2 * tl] > 0) {
      m = tmp[2 * tl];
      w = torig.substr(0, tmp[2 * tl]);
    }
    tmp = prefix_function(trev + "#" + torig);
    if (tmp[2 * tl] > 0 && m < tmp[2 * tl]) {
      m = tmp[2 * tl];
      w = trev.substr(0, tmp[2 * tl]);
    }
    cout << s.substr(0, k) << w << s.substr(l - k, k) << endl;
  }
  return 0;
}
