#include <bits/stdc++.h>
using namespace std;
int precalc = 0;
vector<int> calc_manacher(string str) {
  string nou = "#";
  for (auto c : str) {
    nou.push_back(c);
    nou.push_back('#');
  }
  str = nou;
  vector<int> dp(str.size());
  dp[0] = 1;
  int bestPoz = 0, dreapta = 0;
  for (int i = 1; i < (int)str.size(); ++i) {
    int lg = 1;
    if (i <= dreapta) {
      lg = dp[bestPoz - (i - bestPoz)];
      lg -= max(0, i + lg - 1 - dreapta);
    }
    if (i + lg - 1 >= dreapta)
      while (i - lg >= 0 && i + lg < (int)str.size() &&
             str[i - lg] == str[i + lg])
        ++lg;
    if (i + lg - 1 > dreapta) dreapta = i + lg - 1, bestPoz = i;
    dp[i] = lg;
  }
  return dp;
}
void sol_oficiala(string str, int N) {
  int best = 0;
  while (best < N && str[best] == str[N - 1 - best]) ++best;
  if (best == N) {
    cout << str << '\n';
    return;
  }
  int sol = 1, f1 = 1, t1 = 1, f2 = 1, t2 = 0;
  assert((int)str.size() == N);
  auto manacher = calc_manacher(str);
  for (int i = 1; i + 1 < (int)manacher.size(); ++i) {
    int st = i - manacher[i] + 1, dr = i + manacher[i] - 1;
    assert(st % 2 == 0 && dr % 2 == 0);
    st = st / 2 + 1, dr = dr / 2;
    if (st > dr) continue;
    if (st == 1 && dr == N) {
      sol = N;
      f1 = 1, t1 = N;
      f1 = 1, t2 = 0;
      break;
    }
    if (best + 1 >= st) {
      int lg = dr - st + 1;
      int extra = min(st - 1, N - dr);
      if (extra + 1 >= st) {
        int meh = lg + 2 * extra;
        if (meh > sol) {
          sol = meh, f1 = 1, t1 = dr, f2 = N - extra + 1, t2 = N;
        }
      }
    }
    if (dr + best >= N) {
      int extra = min(N - dr, st - 1);
      int lg = dr - st + 1;
      if (extra + dr >= N) {
        int meh = lg + 2 * extra;
        if (meh > sol) {
          sol = meh;
          f1 = 1, t1 = extra;
          f2 = st, t2 = N;
        }
      }
    }
  }
  int cnt = 0;
  for (int i = f1; i <= t1; ++i) cout << str[i - 1], ++cnt;
  for (int i = f2; i <= t2; ++i) cout << str[i - 1], ++cnt;
  assert(cnt == sol);
  cout << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string str;
    cin >> str;
    sol_oficiala(str, str.size());
  }
  return 0;
}
