#include <bits/stdc++.h>
using namespace std;
int pref[2000500], c;
string solve_palindrome(const string& s) {
  string a = s;
  reverse(a.begin(), a.end());
  a = s + "#" + a;
  c = 0;
  int n = a.length();
  for (int i = 1; i < n; i++) {
    while (c != 0 && a[c] != a[i]) {
      c = pref[c - 1];
    }
    if (a[c] == a[i]) {
      c++;
    }
    pref[i] = c;
  }
  return s.substr(0, c);
}
void solve() {
  string t;
  cin >> t;
  int n = t.length();
  int l = 0;
  while (l < n - l - 1) {
    if (t[l] != t[n - l - 1]) {
      break;
    }
    l++;
  }
  if (l > 0) {
    cout << t.substr(0, l);
  }
  if (n > 2 * l) {
    string s = t.substr(l, n - 2 * l);
    string a = solve_palindrome(s);
    reverse(s.begin(), s.end());
    string b = solve_palindrome(s);
    long long int l1 = a.length();
    long long int l2 = b.length();
    if (l1 < l2) {
      swap(a, b);
    }
    cout << a;
  }
  if (l > 0) {
    cout << t.substr(n - l, l);
  }
  cout << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
