#include <bits/stdc++.h>
using namespace std;
const int max_n = 3 * 1e6;
string s;
int p[max_n];
void manacher(string s) {
  int po, mx, m;
  po = mx = m = 0;
  int i = 0, n = s.size();
  while (i < n) {
    if (i < mx) {
      p[i] = min(mx - i, p[po * 2 - i]);
    } else
      p[i] = 1;
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;
    if (i + p[i] > mx) {
      mx = i + p[i];
      po = i;
    }
    if (i - p[i] == 0 || i + p[i] == n - 1) {
      if (!m || p[i] > p[m]) m = i;
    }
    i++;
  }
  for (int i = m - p[m] + 1; i < m + p[m]; i++) {
    if (s[i] != '#' && s[i] != '@' && s[i] != '$') putchar(s[i]);
  }
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    string s1, s2;
    cin >> s;
    int i = 0, j = s.size() - 1, n = s.size();
    while (s[i] == s[j] && i < j) {
      s1 += s[i];
      s2 += s[j];
      i++;
      j--;
    }
    if (i >= j) {
      cout << s << endl;
      continue;
    }
    string c;
    c += "@#";
    for (int k = i; k <= j; k++) {
      c += s[k];
      c += '#';
    }
    c += '$';
    reverse(s2.begin(), s2.end());
    cout << s1;
    manacher(c);
    cout << s2 << endl;
  }
  return 0;
}
