#include <bits/stdc++.h>
using namespace std;
int longest_palindrome_prefix(const string& s) {
  string kmprev = s;
  std::reverse(kmprev.begin(), kmprev.end());
  string kmp = s + "#" + kmprev;
  vector<int> lps(kmp.size(), 0);
  for (int i = 1; i < (int)lps.size(); ++i) {
    int prev_idx = lps[i - 1];
    while (prev_idx > 0 && kmp[i] != kmp[prev_idx]) {
      prev_idx = lps[prev_idx - 1];
    }
    lps[i] = prev_idx + (kmp[i] == kmp[prev_idx] ? 1 : 0);
  }
  return lps[lps.size() - 1];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout.precision(20);
  long long int tt;
  cin >> tt;
  while (tt--) {
    string s;
    cin >> s;
    long long int n = s.length();
    long long int n1 = 0;
    while ((s[n1] == s[n - 1 - n1]) && (2 * n1 < (n - 1))) n1++;
    ;
    long long int l, r;
    long long int la = 0, ra = 0;
    string q = s.substr(n1, n - 2 * n1);
    string rev = q;
    reverse(rev.begin(), rev.end());
    la = longest_palindrome_prefix(q);
    ra = longest_palindrome_prefix(rev);
    ;
    if (la > ra) {
      l = n1 + la - 1;
      r = n - n1;
    } else {
      l = n1 - 1;
      r = n - (n1 + ra);
    }
    for (long long int i = 0; i < l + 1; i++) cout << s[i];
    for (auto i = r; i <= n - 1; i++) cout << s[i];
    cout << '\n';
  };
  return 0;
}
