#include <bits/stdc++.h>
using namespace std;
int p(string s) {
  string a = s;
  s += "#";
  reverse(a.begin(), a.end());
  s += a;
  int n = s.size();
  vector<int> pi(n);
  pi[0] = 0;
  int j = 0;
  for (int i = 1; i < n; i++) {
    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 j;
}
int main() {
  int t = 1;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int cnt = 0;
    int n = s.size();
    for (int i = 0; i < n / 2; i++) {
      if (s[i] != s[n - 1 - i]) break;
      cnt++;
    }
    string ans;
    if (cnt > 0) cout << s.substr(0, cnt);
    ;
    string a = s;
    reverse(a.begin(), a.end());
    int pos = p(s.substr(cnt, n - 2 * cnt));
    string w = s.substr(cnt, pos);
    pos = p(a.substr(cnt, n - 2 * cnt));
    w = (pos > w.length()) ? a.substr(cnt, pos) : w;
    cout << w;
    if (cnt > 0) cout << s.substr(n - cnt, cnt);
    cout << endl;
  }
}
