#include <bits/stdc++.h>
using namespace std;
const int m = 2e6 + 29;
int pref[m];
string solve_palindrome(string a) {
  string t = a + '#';
  reverse(a.begin(), a.end());
  t = t + a;
  int c = 0, i, l = t.size();
  for (i = 1; i < l; i++) {
    while (c != 0 and t[c] != t[i]) {
      c = pref[c - 1];
    }
    if (t[c] == t[i]) c++;
    pref[i] = c;
  }
  return (t.substr(0, c));
}
void solve() {
  string s;
  cin >> s;
  int i = 0;
  int n = s.size();
  while (i < n - 1 - i) {
    if (s[i] != s[n - 1 - i]) break;
    i++;
  }
  if (i > 0) {
    cout << s.substr(0, i);
  }
  if (n > 2 * i) {
    string t = s.substr(i, n - (2 * i));
    string a = solve_palindrome(t);
    reverse(t.begin(), t.end());
    string b = solve_palindrome(t);
    if (a.size() > b.size())
      cout << a;
    else
      cout << b;
  }
  if (i > 0) {
    cout << s.substr(n - i, i);
  }
  cout << "\n";
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
