#include <bits/stdc++.h>
using namespace std;
string LongestPrefixSuffix(string st) {
  int n = st.length();
  int len = 0;
  int lps[n];
  lps[0] = 0;
  int i = 1;
  while (i < n) {
    if (st[i] == st[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len != 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  return st.substr(0, lps[n - 1]);
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    string st;
    cin >> st;
    int left = 0, right = st.length() - 1;
    string resleft = "";
    while (left < right) {
      if (st[left] != st[right]) {
        break;
      }
      resleft += st[left];
      left++, right--;
    }
    string resmiddle = st.substr(left, right - left + 1);
    string resmiddle2 = st.substr(left, right - left + 1);
    reverse(resmiddle2.begin(), resmiddle2.end());
    string mid1 = LongestPrefixSuffix(resmiddle + "@" + resmiddle2);
    string mid2 = LongestPrefixSuffix(resmiddle2 + "@" + resmiddle);
    string res = resleft;
    if (mid1.length() >= mid2.length()) {
      res += mid1;
    } else {
      res += mid2;
    }
    reverse(resleft.begin(), resleft.end());
    res += resleft;
    cout << res << endl;
  }
}
