#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 10;
int z[MAXN];
void Zvalue(const string &s) {
  z[0] = s.size();
  int l = 0, r = 0, x;
  for (int i = 1; i < s.size(); i++) {
    if (r < i || z[i - l] >= r - i + 1) {
      r < i ? x = i : x = r + 1;
      while (x < s.size() && s[x] == s[x - i]) x++;
      z[i] = x - i;
      if (i < x) {
        l = i;
        r = x - 1;
      };
    } else
      z[i] = z[i - l];
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    string s;
    cin >> s;
    int p;
    for (p = 0; p < s.size() - 1 - p; p++)
      if (s[p] != s[s.size() - 1 - p]) break;
    string smid = s.substr(p, s.size() - p * 2);
    string revsmid = smid;
    reverse(revsmid.begin(), revsmid.end());
    Zvalue(smid + '$' + revsmid);
    int ls = 0, rs = 0;
    for (int i = 1; i <= smid.size(); i++)
      if (i == z[smid.size() * 2 + 1 - i]) ls = i;
    Zvalue(revsmid + '$' + smid);
    for (int i = 1; i <= smid.size(); i++)
      if (i == z[smid.size() * 2 + 1 - i]) rs = i;
    if (ls > rs)
      cout << s.substr(0, p + ls) + s.substr(s.size() - p, p) << '\n';
    else
      cout << s.substr(0, p) + s.substr(s.size() - p - rs, p + rs) << '\n';
  }
}
