#include <bits/stdc++.h>
using namespace std;
int t[2000002];
int longestPrefix(string &s) {
  t[0] = 0;
  for (int pos = 1; pos < s.length(); ++pos) {
    int prev = t[pos - 1];
    while (prev > 0 && s[pos] != s[prev]) {
      prev = t[prev - 1];
    }
    if (s[pos] == s[prev]) {
      t[pos] = prev + 1;
    } else {
      t[pos] = prev;
    }
  }
  return t[s.length() - 1];
}
int main() {
  int t;
  cin >> t;
  while (t-- > 0) {
    string s;
    cin >> s;
    int lindex = 0, rindex = s.length();
    while (lindex < rindex && s[lindex] == s[rindex - 1]) {
      ++lindex;
      --rindex;
    }
    if (lindex >= rindex) {
      cout << s << endl;
      continue;
    }
    string mid = s.substr(lindex, rindex - lindex);
    string rmid = mid;
    reverse(rmid.begin(), rmid.end());
    string pre = mid + '*' + rmid;
    string suf = rmid + '*' + mid;
    int pref = longestPrefix(pre);
    int suff = longestPrefix(suf);
    int len = max(pref, suff);
    for (int i = 0; i < lindex; ++i) {
      cout << s[i];
    }
    if (pref >= suff) {
      for (int i = lindex; i < lindex + pref; ++i) {
        cout << s[i];
      }
    } else {
      for (int i = rindex - suff; i < rindex; ++i) {
        cout << s[i];
      }
    }
    for (int i = rindex; i < s.length(); ++i) {
      cout << s[i];
    }
    cout << endl;
  }
  return 0;
}
