#include <bits/stdc++.h>
using namespace std;
string longest_palindromic_pref_suf(string const& s) {
  const int p = 31;
  const int m = 1e9 + 9;
  int S = s.length(), ret = 0;
  vector<long long> p_pow(S);
  p_pow[0] = 1;
  for (int i = 1; i < (int)p_pow.size(); i++) p_pow[i] = p_pow[i - 1] * p % m;
  long long forward = 0;
  long long backward = 0;
  for (int i = 0; i < S; i++) {
    forward = (forward + (s[i] - 'a' + 1) * p_pow[i]) % m;
    backward = (backward * p + (s[i] - 'a' + 1)) % m;
    if (forward == backward) ret = i;
  }
  string rets = s.substr(0, ret + 1);
  return rets;
}
void solve() {
  string s;
  cin >> s;
  int i, j, flag = 0, S = s.length();
  for (i = 0, j = S - 1; i < j; i++, j--) {
    if (s[i] != s[j]) {
      flag = 1;
      break;
    }
  }
  if (flag) {
    string forward = s.substr(i, S - 2 * i);
    string backward = forward;
    reverse(backward.begin(), backward.end());
    forward = longest_palindromic_pref_suf(forward);
    backward = longest_palindromic_pref_suf(backward);
    string partA = s.substr(0, i);
    string partB = partA;
    string partC = "";
    reverse(partB.begin(), partB.end());
    int F = forward.length();
    int B = backward.length();
    if (F >= B)
      partC = forward;
    else
      partC = backward;
    cout << partA + partC + partB << "\n";
  } else
    cout << s << "\n";
}
int main() {
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}
