#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000005;
struct PAM {
  struct Node {
    int son[27], fail, len, dep;
    void init(int l, int f, int d = 0) {
      fail = f, len = l, dep = d;
      memset(son, 0, sizeof son);
    }
  };
  Node T[N + 5];
  int tot, last, cnt;
  int s[N + 5];
  void init(int n) {
    tot = 1, cnt = 0, last = 0;
    T[0].init(0, 1), T[1].init(-1, 0);
    for (int i = 0; i < n + 1; i++) {
      s[i] = 0;
    }
  }
  void encode(int &c) { c = c - 'a' + 1; }
  int getFail(int cur) {
    while (s[cnt - T[cur].len - 1] != s[cnt]) {
      cur = T[cur].fail;
    }
    return cur;
  }
  void append(int c) {
    encode(c), s[++cnt] = c;
    last = getFail(last);
    if (!T[last].son[c]) {
      int f = getFail(T[last].fail);
      T[++tot].init(T[last].len + 2, T[f].son[c], T[T[f].son[c]].dep + 1);
      T[last].son[c] = tot;
    }
    last = T[last].son[c];
  }
} pam;
vector<int> z_function(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; i++) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}
int main() {
  cin.sync_with_stdio(false), cin.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int n = s.length();
    string t = s;
    reverse(t.begin(), t.end());
    auto z = z_function(t + "#" + s);
    int lcf = z[n + 1];
    if (lcf == n) {
      cout << s << "\n";
      continue;
    }
    int l = lcf, r = lcf;
    pam.init(n);
    for (int i = lcf; i < n - lcf; i++) {
      pam.append(s[i]);
      if (pam.T[pam.last].len == i - lcf + 1) {
        r = i;
      }
    }
    pam.init(n);
    for (int i = n - lcf - 1; i >= lcf; i--) {
      pam.append(s[i]);
      int len = pam.T[pam.last].len;
      if (len == n - lcf - i && len > r - l + 1) {
        l = i, r = n - lcf - 1;
      }
    }
    string res =
        s.substr(0, lcf) + s.substr(l, r - l + 1) + s.substr(n - lcf, lcf);
    cout << res << "\n";
  }
}
