#include <bits/stdc++.h>
using namespace std;
vector<char> Manacher(string s) {
  vector<char> ass;
  string t = "$#";
  for (int i = 0; i < s.size(); ++i) {
    t += s[i];
    t += "#";
  }
  vector<int> p(t.size(), 0);
  int mx = 0, mid = 0;
  for (int i = 1; i < t.size(); ++i) {
    p[i] = mx > i ? min(p[2 * mid - i], mx - i) : 1;
    while (t[i + p[i]] == t[i - p[i]]) ++p[i];
    if (mx < i + p[i]) {
      mx = i + p[i];
      mid = i;
    }
  }
  int tp = 0;
  int tas = 0;
  for (int i = 1; i < t.size(); i++) {
    if (p[i] > tp && (p[i] == i || p[i] == t.size() - i)) {
      tas = i;
      tp = p[i];
    }
  }
  for (int i = (tas - p[tas] + 1); i <= (tas + p[tas] - 1); i++) {
    ass.push_back(t[i]);
  }
  return ass;
}
int main() {
  ios::sync_with_stdio(false);
  long long T;
  cin >> T;
  while (T--) {
    string s;
    cin >> s;
    vector<char> as;
    vector<char> as2;
    long long n = s.size();
    long long l = 0, r = n - 1;
    for (long long i = 0; i < n; i++) {
      if (l > r) break;
      if (s[l] == s[r]) {
        as.push_back(s[l]);
        l += 1;
        r -= 1;
      } else {
        break;
      }
    }
    if (r < l) {
      cout << s << endl;
      continue;
    }
    string x(s, l, r - l + 1);
    as2 = Manacher(x);
    for (long long i = 0; i < as.size(); i++) {
      cout << as[i];
    }
    for (long long i = 0; i < as2.size(); i++) {
      if (as2[i] != '#') cout << as2[i];
    }
    if (as.size() > 0) {
      for (long long i = as.size() - 1; i >= 0; i--) {
        cout << as[i];
      }
    }
    cout << endl;
  }
  return 0;
}
