#include <bits/stdc++.h>
using namespace std;
long long int palindrome_find(string str) {
  string temp = str + '?';
  reverse(str.begin(), str.end());
  temp += str;
  long long int lps[temp.size()];
  lps[0] = 0;
  for (long long int i = 1; i < temp.size(); i++) {
    long long int j = lps[i - 1];
    while (j > 0 && temp[i] != temp[j]) j = lps[j - 1];
    if (temp[i] == temp[j]) j++;
    lps[i] = j;
  }
  return lps[temp.size() - 1];
}
int32_t main() {
  long long int test;
  cin >> test;
  while (test--) {
    string str;
    cin >> str;
    long long int l = 0;
    for (long long int i = 0, j = str.size() - 1; i < j; j--, i++)
      if (str[i] == str[j])
        l++;
      else
        break;
    string ans = str.substr(0, l);
    string temp = ans;
    string rem = str.substr(l, str.size() - 2 * l);
    if (rem.size()) {
      long long int pre = palindrome_find(rem);
      reverse(rem.begin(), rem.end());
      long long int suf = palindrome_find(rem);
      if (pre > suf) {
        ans += str.substr(l, pre);
      } else
        ans += rem.substr(0, suf);
    }
    reverse(temp.begin(), temp.end());
    cout << ans << temp << endl;
  }
}
