#include <bits/stdc++.h>
using namespace std;
const long long int mxn = 1e5 + 5;
long long int lps(string s) {
  string x = s + '?';
  reverse(s.begin(), s.end());
  x += s;
  long long int n = x.length();
  long long int pre[n];
  pre[0] = 0;
  for (long long int i = 1; i < n; i++) {
    long long int j = pre[i - 1];
    while (j > 0 && x[j] != x[i]) j = pre[j - 1];
    if (x[i] == x[j]) j++;
    pre[i] = j;
  }
  return pre[n - 1];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int t = 1;
  cin >> t;
  while (t--) {
    long long int i, j, k, n, m;
    string s;
    cin >> s;
    n = s.length();
    i = 0, j = n - 1;
    while (i < j && s[i] == s[j]) i++, j--;
    long long int p1 = lps(s.substr(i, j - i + 1));
    reverse(s.begin() + i, s.begin() + j + 1);
    long long int p2 = lps(s.substr(i, j - i + 1));
    reverse(s.begin() + i, s.begin() + j + 1);
    string ans;
    for (long long int j = 0; j < i; j++) ans += s[j];
    if (p1 > p2) {
      for (long long int j = 0; j < p1; j++) ans += s[i + j];
    } else {
      for (long long int i = 0; i < p2; i++) ans += s[j - i];
    }
    for (long long int i = j + 1; i < n; i++) ans += s[i];
    cout << ans << "\n";
  }
  return 0;
}
