#include <bits/stdc++.h>
using namespace std;
inline void Boost() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
const int NMax = 1e6 + 50;
string convert(const string &s) {
  string ret = "@";
  for (int i = 0; i < (int)s.size(); ++i) {
    ret += "#" + s.substr(i, 1);
  }
  ret += "#$";
  return ret;
}
int P[NMax * 2];
void Solve() {
  string s;
  cin >> s;
  int n = (int)s.size();
  int a = 0;
  int b = n - 1;
  while (a <= b) {
    if (a == b) {
      cout << s << "\n";
      return;
    }
    if (s[a] == s[b]) {
      ++a;
      --b;
      if (a > b) {
        cout << s << "\n";
        return;
      }
    } else {
      string nw = convert(s);
      int cen = 0, r = 0;
      for (int i = 0; i < (int)nw.size(); ++i) P[i] = 0;
      for (int i = 1; i < (int)nw.size() - 1; ++i) {
        int mir = cen - (i - cen);
        if (r > i) {
          P[i] = min(r - i, P[mir]);
        }
        while (nw[i + 1 + P[i]] == nw[i - 1 - P[i]]) {
          P[i]++;
        }
        if (i + P[i] > r) {
          cen = i;
          r = i + P[i];
        }
      }
      int best = 0;
      int pos = 0;
      for (int i = 1; i < (int)nw.size() - 1; i++) {
        int start = (i - 1 - P[i]) / 2;
        int fin = start + P[i] - 1;
        if (start < a) {
          int mv = a - start;
          start += mv;
          fin -= mv;
        }
        if (fin > b) {
          int mv = fin - b;
          start += mv;
          fin -= mv;
        }
        if (start != a && fin != b) continue;
        if (start <= fin && (fin - start + 1) > best) {
          best = fin - start + 1;
          pos = start;
        }
      }
      for (int i = 0; i < a; ++i) cout << s[i];
      for (int i = pos; i < pos + best; ++i) cout << s[i];
      for (int i = a - 1; i >= 0; --i) cout << s[i];
      cout << "\n";
      return;
    }
  }
}
int main() {
  Boost();
  int t;
  cin >> t;
  while (t--) {
    Solve();
  }
  return 0;
}
