#include <bits/stdc++.h>
using namespace std;
int nt, n;
char s[1000010];
struct Manachar {
  int n;
  vector<int> d;
  vector<int> e;
  int build(char* s) {
    n = strlen(s), d.resize(n), e.resize(n);
    int res = 0;
    int l = 0, r = -1;
    for (int i = 0; i < n; ++i) {
      int k = (i > r) ? 1 : min(d[l + r - i], r - i) + 1;
      while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k++;
      d[i] = --k;
      res = max(res, k + k + 1);
      if (r < i + k) {
        l = i - k;
        r = i + k;
      }
    }
    l = 0;
    r = -1;
    for (int i = 0; i < n; ++i) {
      int k = (i > r) ? 1 : min(e[l + r - i + 1], r - i + 1) + 1;
      while (i - k >= 0 && i + k - 1 < n && s[i - k] == s[i + k - 1]) k++;
      e[i] = --k;
      res = max(res, k + k);
      if (r < i + k - 1) {
        l = i - k;
        r = i + k - 1;
      }
    }
    return res;
  }
} mnc;
vector<int> f[1000010];
vector<int> g[1000010];
int main() {
  ios::sync_with_stdio(false);
  cin >> nt;
  while (nt--) {
    cin >> s;
    mnc.build(s);
    n = mnc.n;
    for (int i = 0; i < n; i++) {
      f[i].clear();
      g[i].clear();
      f[i].push_back(i);
      g[i].push_back(i);
    }
    for (int i = 0; i < mnc.n; i++)
      if (mnc.d[i] > 0) {
        int l = i - mnc.d[i];
        int r = i + mnc.d[i];
        f[l].push_back(r);
        g[r].push_back(l);
      }
    for (int i = 0; i < mnc.n; i++)
      if (mnc.e[i] > 0) {
        int l = i - mnc.e[i];
        int r = i + mnc.e[i] - 1;
        f[l].push_back(r);
        g[r].push_back(l);
      }
    int prefix = 1;
    int suffix = 0;
    int l = 0;
    int r = n - 1;
    while (true) {
      int mx_prefix = -1;
      int mn_suffix = n + 1;
      for (int i = 0; i < (int)f[l].size(); i++) {
        if (f[l][i] <= r) {
          mx_prefix = max(mx_prefix, f[l][i]);
        }
      }
      for (int i = 0; i < (int)g[r].size(); i++) {
        if (g[r][i] >= l) {
          mn_suffix = min(mn_suffix, g[r][i]);
        }
      }
      if (mx_prefix > -1) {
        int nw_prefix = mx_prefix + 1;
        int nw_suffix = (n - 1 - r);
        if (nw_prefix + nw_suffix > prefix + suffix) {
          prefix = nw_prefix;
          suffix = nw_suffix;
        }
      }
      if (mn_suffix < n) {
        int nw_prefix = l;
        int nw_suffix = n - mn_suffix;
        if (nw_prefix + nw_suffix > prefix + suffix) {
          prefix = nw_prefix;
          suffix = nw_suffix;
        }
      }
      if (s[l] != s[r]) break;
      l++;
      r--;
      if (l > r) break;
      int nw_prefix = l;
      int nw_suffix = (n - 1 - r);
      if (nw_prefix + nw_suffix > prefix + suffix) {
        prefix = nw_prefix;
        suffix = nw_suffix;
      }
    }
    for (int i = 0; i < prefix; i++) cout << s[i];
    for (int i = n - suffix; i < n; i++) cout << s[i];
    cout << "\n";
  }
  return 0;
}
