#include <bits/stdc++.h>
using namespace std;
vector<int> KMP(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}
int main() {
  int n, x, k, j = 0;
  int t;
  cin >> t;
  while (t--) {
    string a;
    cin >> a;
    int n = a.length();
    int l = 0, r = a.length() - 1;
    while (a[l] == a[r]) l++, r--;
    if (2 * l >= n) {
      cout << a << '\n';
      continue;
    }
    string ans = a.substr(0, l);
    string mm = ans;
    string x = a.substr(l, n - 2 * l);
    string y = x;
    reverse(x.begin(), x.end());
    string kmp1 = y + '#' + x;
    string kmp2 = x + '#' + y;
    vector<int> a1 = KMP(kmp1);
    vector<int> b1 = KMP(kmp2);
    int aa = a1.back();
    int bb = b1.back();
    if (aa > bb) {
      ans += y.substr(0, aa);
    } else
      ans += x.substr(0, bb);
    reverse(mm.begin(), mm.end());
    ans += mm;
    cout << ans << "\n";
  }
}
