#include <bits/stdc++.h>
using namespace std;
long long mod = 998244353;
long long kmp(string x) {
  long long n = x.length();
  vector<long long> lcp(x.length(), 0);
  for (long long i = 1; i < n; i++) {
    long long j = lcp[i - 1];
    while (j > 0 && x[j] != x[i]) j = lcp[j - 1];
    if (x[i] == x[j]) j++;
    lcp[i] = j;
  }
  return lcp[n - 1];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    string a;
    cin >> a;
    string b = a;
    reverse(a.begin(), a.end());
    long long i = 0;
    for (i = 0; i < a.length(); i++)
      if (a[i] != b[i]) break;
    if (i == a.length())
      cout << b << endl;
    else {
      string x = b.substr(i, b.length() - i);
      x.erase(x.end() - i, x.end());
      string y = a.substr(i, a.length() - i);
      y.erase(y.end() - i, y.end());
      long long a1 = kmp(x + '#' + y);
      long long a2 = kmp(y + '#' + x);
      string ans = b.substr(0, i);
      if (a1 >= a2)
        ans += x.substr(0, a1);
      else {
        ans += y.substr(0, a2);
      }
      ans += b.substr(b.length() - i, i);
      cout << ans << endl;
    }
  }
  return 0;
}
