#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;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int lencommon = 0;
    int n = s.size();
    for (int i = 0; i < n / 2; ++i) {
      if (s[i] == s[n - i - 1]) {
        lencommon = i + 1;
      } else {
        break;
      }
    }
    string a = s.substr(lencommon, s.size() - 2 * lencommon);
    string areverse = a;
    reverse(areverse.begin(), areverse.end());
    string a1 = a + "$" + areverse;
    vector<int> kmp1 = prefix_function(a1);
    int len1 = lencommon + kmp1[2 * a.size()];
    string a2 = areverse + "$" + a;
    vector<int> kmp2 = prefix_function(a2);
    int len2 = lencommon + kmp2[2 * a.size()];
    if (len1 >= len2) {
      cout << s.substr(0, len1) + s.substr(n - lencommon, lencommon) << endl;
    } else {
      cout << s.substr(0, lencommon) + s.substr(s.size() - len2, len2) << endl;
    }
  }
}
