#include <bits/stdc++.h>
using namespace std;
int kmp(string s) {
  vector<int> lps(s.size(), 0);
  for (int i = 1; i < s.size(); ++i) {
    int index = lps[i - 1];
    while (index > 0 && s[i] != s[index]) index = lps[index - 1];
    if (s[i] == s[index])
      lps[i] = index + 1;
    else
      lps[i] = index;
  }
  return lps[lps.size() - 1];
}
int func(string s) {
  string t = s + "#";
  reverse(s.begin(), s.end());
  t += s;
  return kmp(t);
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int l = 0, n = s.length();
    for (int i = 0, j = n - 1; i < j; i++, j--) {
      if (s[i] == s[j])
        l++;
      else
        break;
    }
    string remaining = s.substr(l, n - 2 * l);
    string ans = s.substr(0, l);
    if (remaining.size()) {
      int lp = func(remaining);
      reverse(remaining.begin(), remaining.end());
      int ls = func(remaining);
      if (lp > ls) {
        reverse(remaining.begin(), remaining.end());
        ans += remaining.substr(0, lp);
      } else
        ans += remaining.substr(0, ls);
    }
    ans += s.substr(n - l, l);
    cout << ans << endl;
  }
}
