#include <bits/stdc++.h>
using namespace std;
int __i__, __j__;
class _Debug {
 public:
  template <typename T>
  _Debug& operator,(T val) {
    cout << val << endl;
    return *this;
  }
};
int L[3000000];
int Manacher(string s) {
  int N = 2 * s.size() + 1;
  int i, j = 1;
  L[0] = 0, L[1] = 1;
  for (i = 2; i < N; i++) {
    L[i] = max(min(L[2 * j - i], j + L[j] - i), 0);
    while (((i + L[i]) < N) && (L[i] < i) &&
           ((((i + L[i]) % 2) == 1) ||
            (s[(i + L[i] + 1) / 2] == s[(i - L[i] - 1) / 2])))
      L[i]++;
    if ((i + L[i]) > (j + L[j])) j = i;
  }
  return 0;
}
int main() {
  cin.sync_with_stdio(0);
  int i;
  int t;
  string s;
  cin >> t;
  while (t--) {
    cin >> s;
    i = 0;
    while ((i < s.size() / 2) && (s[i] == s[s.size() - i - 1])) i++;
    if (i >= s.size() / 2)
      cout << s << endl;
    else {
      int p = i;
      string t = s.substr(p, s.size() - 2 * p);
      Manacher(t);
      int pre = 0, suff = 0;
      for (i = 0; i < 2 * t.size() + 1; i++) {
        if (L[i] == i) pre = i;
      }
      for (i = 2 * t.size(); i >= 0; i--) {
        if (L[i] == 2 * t.size() - i) suff = 2 * t.size() - i;
      }
      if (pre > suff)
        cout << s.substr(0, p) << s.substr(p, pre) << s.substr(s.size() - p, p)
             << endl;
      else
        cout << s.substr(0, p) << s.substr(s.size() - p - suff, suff)
             << s.substr(s.size() - p, p) << endl;
    }
  }
  return 0;
}
