#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7, MAX = 1e5 + 5;
long long powN(long long a, long long p) {
  if (p == 0) return 1;
  long long z = powN(a, p / 2);
  z = (z * z) % MOD;
  if (p % 2) z = (z * a) % MOD;
  return z;
}
vector<bool> is_prime(MAX + 1, true);
void Sieve() {
  is_prime[0] = is_prime[1] = false;
  int i, j;
  for (i = 2; i * i <= MAX; i++) {
    if (is_prime[i]) {
      for (j = i * i; j <= MAX; j += i) is_prime[j] = false;
    }
  }
}
int lps(string s) {
  int n = s.length();
  vector<int> lp(n + 5);
  lp[0] = 0;
  int len = 0;
  int i = 1;
  while (i < n) {
    if (s[i] == s[len]) {
      len++;
      lp[i] = len;
      i++;
    } else {
      if (len != 0) {
        len = lp[len - 1];
      } else {
        lp[i] = 0;
        i++;
      }
    }
  }
  int res = lp[n - 1];
  return (res > n / 2) ? n / 2 : res;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int n = s.length();
    string s1, s2;
    int st = 0, en = n - 1;
    for (int i = 0; i < n / 2; i++) {
      if (s[i] == s[n - 1 - i]) {
        st++;
        en--;
        s1.push_back(s[i]);
        s2.push_back(s[n - 1 - i]);
      } else {
        st = i;
        en = n - 1 - i;
        break;
      }
    }
    int ans1 = 0;
    int ans2 = 0;
    string ss1 = s.substr(st, en - st + 1);
    string ss2 = ss1;
    reverse(ss2.begin(), ss2.end());
    string ss3 = ss1 + '#' + ss2;
    ans1 = lps(ss3);
    string ss4 = ss2 + '#' + ss1;
    ans2 = lps(ss4);
    if (ans1 > ans2) {
      string S = ss3.substr(0, ans1);
      reverse(s2.begin(), s2.end());
      cout << s1 << S << s2 << endl;
    } else {
      string S = ss4.substr(0, ans2);
      reverse(s2.begin(), s2.end());
      cout << s1 << S << s2 << endl;
    }
  }
}
