#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e6 + 5;
int pre[N];
int solve_KMP(const string st) {
  string s;
  s = st;
  reverse(s.begin(), s.end());
  s = (st + "#" + s);
  int c = 0;
  for (int i = 1; i < s.size(); i++) {
    while (c > 0 and s[c] != s[i]) c = pre[c - 1];
    if (s[c] == s[i]) c++;
    pre[i] = c;
  }
  return c;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int test;
  cin >> test;
  while (test--) {
    string s;
    cin >> s;
    int n = s.size();
    int lb = 0, rb = n - 1;
    while (lb < rb and s[lb] == s[rb]) lb++, rb--;
    if (lb > 0) cout << s.substr(0, lb);
    if (2 * lb < n) {
      string st = s.substr(lb, rb - lb + 1);
      int len = 0;
      len = solve_KMP(st);
      string a = st.substr(0, len);
      reverse(st.begin(), st.end());
      len = solve_KMP(st);
      string b = st.substr(0, len);
      if (a.size() > b.size())
        cout << a;
      else
        cout << b;
    }
    cout << s.substr(rb + 1);
    cout << "\n";
  }
  return 0;
}
