#include <bits/stdc++.h>
using namespace std;
long long lps(string str) {
  long long n = str.length(), i = 1, len = 0, j = 0;
  long long lps[n];
  lps[0] = 0;
  while (i < n) {
    if (str[i] == str[j]) {
      lps[i] = j + 1;
      i++;
      j++;
    } else if (j == 0)
      lps[i] = 0, i++;
    else
      j = lps[j - 1];
  }
  return lps[n - 1];
}
void solve() {
  string str, s1, s2, s3, s4;
  cin >> str;
  long long n = str.length();
  long long i = 0, j = n - 1, len = n, val;
  while (i <= j) {
    if (str[i] != str[j]) break;
    len -= 2;
    if (i == j) len++;
    i++;
    j--;
  }
  val = i;
  if (!len) {
    cout << str << endl;
    return;
  }
  s1 = s2 = str.substr(i, len);
  reverse(s2.begin(), s2.end());
  s3 = s1 + '*' + s2;
  s4 = s2 + '*' + s1;
  long long len1 = lps(s3);
  long long len2 = lps(s4);
  if (len1 >= len2)
    cout << (str.substr(0, val) + s3.substr(0, len1) + str.substr(n - val))
         << endl;
  else
    cout << (str.substr(0, val) + s4.substr(0, len2) + str.substr(n - val))
         << endl;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  long long t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
