#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ll = long long int;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using cdouble = complex<double>;
const double eps = 1e-7;
bool feq(double x, double y) { return abs(x - y) <= eps; }
bool inrange(ll x, ll t) { return x >= 0 && x < t; }
bool inrange(vll xs, ll t) {
  for (const auto &x : xs)
    if (!(x >= 0 && x < t)) return false;
  return true;
}
int ceillog2(ll x) { return int(ceil(log2(x))); }
int floorlog2(ll x) { return int(floor(log2(x))); }
template <class T>
T reversed(T container) {
  reverse(container.begin(), container.end());
  return container;
}
template <class T>
void printv(const vector<T> &v) {
  for (const T &x : v) cout << x << " ";
  cout << "\n";
}
template <class T>
void printmx(const vector<vector<T>> &mx) {
  for (const vector<T> &v : mx) printv(v);
}
ll rndf(double x) { return (ll)(x + (x >= 0 ? 0.5 : -0.5)); }
ll floorsqrt(ll x) {
  ll m = (ll)sqrt((double)x);
  return m + (m * m <= x ? 0 : -1);
}
ll ceilsqrt(ll x) {
  ll m = (ll)sqrt((double)x);
  return m + (x <= m * m ? 0 : 1);
}
ll rnddiv(ll a, ll b) { return (a / b + (a % b * 2 >= b ? 1 : 0)); }
ll ceildiv(ll a, ll b) { return (a / b + (a % b == 0 ? 0 : 1)); }
ll gcd(ll m, ll n) {
  if (n == 0)
    return m;
  else
    return gcd(n, m % n);
}
ll lcm(ll m, ll n) { return m * n / gcd(m, n); }
class Random_Int {
 private:
  mt19937 *mt;
  uniform_int_distribution<> *distr_int;

 public:
  Random_Int(int m) {
    mt = new std::mt19937(
        (unsigned)(std::chrono::duration_cast<chrono::nanoseconds>(
                       chrono::high_resolution_clock::now().time_since_epoch())
                       .count()));
    distr_int = new uniform_int_distribution<>(0, m - 1);
  }
  int get() { return (*distr_int)(*mt); }
};
class String_Comparator {
 private:
  const vll MOD_cands = {1000000007, 1000000403, 1000000787, 1000001447,
                         1000001819, 1000002359, 1000002803, 1000003919,
                         1000004207, 1000004519};
  ll MOD;
  int max_length;
  vll bases;
  vvll pows;
  Random_Int *ri;

 public:
  String_Comparator(int max_length, int n_base = 3) {
    Random_Int *rm = new Random_Int(int(MOD_cands.size()));
    this->MOD = this->MOD_cands[rm->get()];
    this->max_length = max(1, max_length);
    this->ri = new Random_Int(int(this->MOD) - 256);
    this->bases.resize(n_base);
    this->pows.resize(n_base, vll(this->max_length + 1));
    for (int k = 0; k < int(n_base); k++) {
      this->bases[k] = this->ri->get() + 256;
      this->pows[k][0] = 1;
      for (int i = 1; i <= int(this->max_length); i++) {
        pows[k][i] = pows[k][i - 1] * this->bases[k] % this->MOD;
      }
    }
  }
  vvll make_hashs(const string &s) {
    int n = int(s.length());
    vvll ret(this->bases.size(), vll(n + 1));
    for (int k = 0; k < int(this->bases.size()); k++) {
      for (int i = 1; i <= int(n); i++) {
        ret[k][i] = (ret[k][i - 1] * this->bases[k] + s[i - 1]) % this->MOD;
      }
    }
    return ret;
  }
  bool is_equal(const vvll &hashs0, const vvll &hashs1, const int s0,
                const int s1, const int l) {
    for (int k = 0; k < int(this->bases.size()); k++) {
      ll val0 = (hashs0[k][s0 + l] - hashs0[k][s0] * pows[k][l]) % this->MOD;
      ll val1 = (hashs1[k][s1 + l] - hashs1[k][s1] * pows[k][l]) % this->MOD;
      if (val0 < 0) val0 += this->MOD;
      if (val1 < 0) val1 += this->MOD;
      if (val0 != val1) return false;
    }
    return true;
  }
  vll get_hashs(const vvll &hashs, const int s, const int l) {
    vll ret(bases.size());
    for (int k = 0; k < int(this->bases.size()); k++) {
      ret[k] = (hashs[k][s + l] - hashs[k][s] * pows[k][l]) % this->MOD;
      if (ret[k] < 0) ret[k] += this->MOD;
    }
    return ret;
  }
};
template <class val_t, class bsargv_t>
val_t lower_bsearch(val_t l, val_t r, const bsargv_t &v,
                    bool (*evalfunc)(val_t, const bsargv_t &)) {
  if (r - l == 1) {
    if (evalfunc(l, v))
      return l;
    else
      return l - 1;
  }
  val_t m = (l + r) / 2;
  if (evalfunc(m, v))
    return lower_bsearch<val_t, bsargv_t>(m, r, v, evalfunc);
  else
    return lower_bsearch<val_t, bsargv_t>(l, m, v, evalfunc);
}
struct bsargv_t {
  int n;
  String_Comparator *sc;
  vvll hashs0, hashs1;
  int i0, i1;
};
bool evalfunc(int val, const bsargv_t &v) {
  if (v.i0 + val <= v.n && v.i1 + val <= v.n &&
      v.sc->is_equal(v.hashs0, v.hashs1, v.i0, v.i1, val)) {
    return true;
  } else {
    return false;
  }
}
struct ans_t {
  int l, r;
  bool operator<(const ans_t &another) const {
    return (l + r < another.l + another.r);
  }
};
string core(int n, const string &s, const vi &os, const vi &es) {
  ans_t ans = {1, 0};
  vi oseq(n / 2 + 2, -1);
  vi eseq(n / 2 + 2, -1);
  for (int i = 0; i < int(ceildiv(n, 2)); i++) {
    if (os[i] > 0) {
      oseq[i - os[i] + 1] = max(oseq[i - os[i] + 1], i);
    }
  }
  for (int i = 0; i < int(n / 2); i++) {
    if (es[i] > 0) {
      eseq[i - es[i] + 1] = max(eseq[i - es[i] + 1], i);
    }
  }
  bool is_par = true;
  int omax = -1, emax = -1;
  for (int i = 0; i < int(n / 2 + 1); i++) {
    omax = max(omax, oseq[i]);
    emax = max(emax, eseq[i]);
    ans_t buf = {i, i};
    ans = max(ans, buf);
    if (omax >= 0) {
      int ro = omax;
      if (ro >= i) {
        ans_t bufo = buf;
        bufo.l += (ro - i + 1) * 2 - 1;
        ans = max(ans, bufo);
      }
    }
    if (emax >= 0) {
      int re = emax;
      if (re >= i) {
        ans_t bufe = buf;
        bufe.l += (re - i + 1) * 2;
        ans = max(ans, bufe);
      }
    }
    if (i >= n - 1 - i || s[i] != s[n - 1 - i]) {
      is_par = false;
      break;
    }
  }
  return s.substr(0, ans.l) + s.substr(n - ans.r, ans.r);
}
string solve(bsargv_t &v) {
  string s;
  cin >> s;
  string t = s;
  reverse(t.begin(), t.end());
  v.n = s.length();
  v.hashs0 = v.sc->make_hashs(s);
  v.hashs1 = v.sc->make_hashs(t);
  vi os(v.n), es(v.n);
  for (int i = 0; i < int(v.n); i++) {
    v.i0 = i;
    v.i1 = v.n - 1 - i;
    os[i] = lower_bsearch(0, v.n, v, evalfunc);
  }
  for (int i = 0; i < int(v.n - 1); i++) {
    v.i0 = i + 1;
    v.i1 = v.n - 1 - i;
    es[i] = lower_bsearch(0, v.n, v, evalfunc);
  }
  string ans0 = core(v.n, s, os, es);
  reverse(os.begin(), os.end());
  reverse(es.begin(), es.end());
  for (int i = 0; i < int(v.n - 1); i++) {
    es[i] = es[i + 1];
  }
  es[v.n - 1] = 0;
  string ans1 = core(v.n, t, os, es);
  reverse(ans1.begin(), ans1.end());
  string ans = (ans0.length() >= ans1.length() ? ans0 : ans1);
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ;
  int n;
  cin >> n;
  bsargv_t v;
  v.sc = new String_Comparator(1000003);
  for (int _ = 0; _ < int(n); _++) {
    cout << solve(v) << "\n";
  }
}
