#include <bits/stdc++.h>
using namespace std;
const long long int inf = 9e18;
const long double pi = 2 * acos(0.0);
long long int pre[100005];
string checkPalindrome(string p1) {
  string s1 = p1;
  reverse(s1.begin(), s1.end());
  s1 = p1 + "*" + s1;
  long long int pos = 0;
  for (long long int i = 1; i < s1.size(); ++i) {
    while (pos != 0 && s1[pos] != s1[i]) pos = pre[pos - 1];
    if (s1[pos] == s1[i]) pos++;
    pre[i] = pos;
  }
  return s1.substr(0, pos);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int tc;
  cin >> tc;
  while (tc--) {
    string str;
    cin >> str;
    long long int len = str.length();
    for (long long int i = 0; i < len; ++i) pre[i] = 0;
    long long int l = 0;
    while (l < len - l - 1) {
      if (str[l] != str[len - l - 1]) break;
      l++;
    }
    if (l > 0) cout << str.substr(0, l);
    if (len > 2 * l) {
      string p1 = str.substr(l, len - 2 * l);
      string a = checkPalindrome(p1);
      string p2 = p1;
      reverse(p2.begin(), p2.end());
      string b = checkPalindrome(p2);
      if (a.size() < b.size())
        cout << b;
      else
        cout << a;
    }
    if (l > 0) cout << str.substr(str.size() - l, l);
    cout << "\n";
  }
}
