#include <bits/stdc++.h>
using namespace std;
inline long long isqrt(long long k) {
  long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline long long mnz(long long& a, long long b) { return a = (a > b ? b : a); }
inline long long mxz(long long& a, long long b) { return a = (a < b ? b : a); }
inline string toString(long long n) {
  stringstream ss;
  ss << n;
  return ss.str();
}
double const eps = 1e-6;
long long const Base1 = 1000000097, Base2 = 1000500097, oo = 1e17, MAXN = 1e6;
pair<long long, long long> POW[MAXN + 5];
pair<long long, long long> HASH[MAXN + 5];
pair<long long, long long> HASH2[MAXN + 5];
pair<long long, long long> R1[MAXN + 5], R2[MAXN + 5];
pair<long long, long long> L1[MAXN + 5], L2[MAXN + 5];
pair<long long, long long> inline getHASH(long long i, long long j) {
  if (i > j) return make_pair(0, 0);
  return make_pair(
      (HASH[j].first - HASH[i - 1].first * POW[j - i + 1].first +
       Base1 * Base1) %
          Base1,
      (HASH[j].second - HASH[i - 1].second * POW[j - i + 1].second +
       Base2 * Base2) %
          Base2);
}
pair<long long, long long> inline getHASH2(long long i, long long j) {
  if (i > j) return make_pair(0, 0);
  return make_pair(
      (HASH2[i].first - HASH2[j + 1].first * POW[j - i + 1].first +
       Base1 * Base1) %
          Base1,
      (HASH2[i].second - HASH2[j + 1].second * POW[j - i + 1].second +
       Base2 * Base2) %
          Base2);
}
long long Solves() {
  string s, anss1 = "", anss2 = "";
  cin >> s;
  long long ls = s.length();
  s = " " + s;
  for (long long i = 1; i <= ls; i++)
    HASH[i] = make_pair((HASH[i - 1].first * 29 + s[i] - 'a' + 1) % Base1,
                        (HASH[i - 1].second * 29 + s[i] - 'a' + 1) % Base2);
  HASH2[ls + 1] = make_pair(0, 0);
  for (long long i = ls; i >= 1; i--)
    HASH2[i] = make_pair((HASH2[i + 1].first * 29 + s[i] - 'a' + 1) % Base1,
                         (HASH2[i + 1].second * 29 + s[i] - 'a' + 1) % Base2);
  for (long long i = ls + 1; i >= 1; i--) {
    R1[i] = getHASH(i, ls);
    R2[i] = getHASH2(i, ls);
  }
  for (long long i = 0; i <= ls; i++) {
    L1[i] = getHASH(1, i);
    L2[i] = getHASH2(1, i);
  }
  {
    long long n, m, k, cnt = 0, ans = 0, x, y, q, c, sum = 0, v, t;
    v = 0;
    t = ls + 1;
    long long l = 0, r = ls, mid;
    while (l <= r) {
      mid = (l + r) / 2;
      q = 0;
      long long i = mid;
      {
        pair<long long, long long> v1 = L1[i];
        pair<long long, long long> v4 = L2[i];
        if (i > mid) break;
        for (long long j = ls - i + 1; j >= i + 1; j--) {
          pair<long long, long long> v2 = R1[j];
          pair<long long, long long> v3 = make_pair(
              (v1.first * POW[max(0LL, ls - j + 1)].first + v2.first) % Base1,
              (v1.second * POW[max(0LL, ls - j + 1)].second + v2.second) %
                  Base2);
          pair<long long, long long> v5 = R2[j];
          pair<long long, long long> v6 = make_pair(
              (v5.first * POW[max(0LL, i)].first + v4.first) % Base1,
              (v5.second * POW[max(0LL, i)].second + v4.second) % Base2);
          if (v3 == v6) {
            q = 1;
            if (v + ls + 1 - t < i + ls + 1 - j) v = i, t = j;
          }
        }
      }
      if (q)
        l = mid + 1;
      else
        r = mid - 1;
    }
    for (long long i = 1; i <= v; i++) anss1.push_back(s[i]);
    for (long long i = t; i <= ls; i++) anss1.push_back(s[i]);
  }
  {
    long long n, m, k, cnt = 0, ans = 0, x, y, q, c, sum = 0, v, t;
    v = 0;
    t = ls + 1;
    long long l = 0, r = ls, mid;
    while (l <= r) {
      mid = (l + r) / 2;
      q = 0;
      long long j = ls - mid + 1;
      {
        pair<long long, long long> v2 = R1[j];
        pair<long long, long long> v5 = R2[j];
        for (long long i = mid; i <= j - 1; i++) {
          pair<long long, long long> v1 = L1[i];
          pair<long long, long long> v3 = make_pair(
              (v1.first * POW[max(0LL, ls - j + 1)].first + v2.first) % Base1,
              (v1.second * POW[max(0LL, ls - j + 1)].second + v2.second) %
                  Base2);
          pair<long long, long long> v4 = L2[i];
          pair<long long, long long> v6 = make_pair(
              (v5.first * POW[max(0LL, i)].first + v4.first) % Base1,
              (v5.second * POW[max(0LL, i)].second + v4.second) % Base2);
          if (v3 == v6) {
            q = 1;
            if (v + ls + 1 - t < i + ls + 1 - j) v = i, t = j;
          }
        }
      }
      if (q)
        l = mid + 1;
      else
        r = mid - 1;
    }
    for (long long i = 1; i <= v; i++) anss2.push_back(s[i]);
    for (long long i = t; i <= ls; i++) anss2.push_back(s[i]);
  }
  if ((long long)anss1.length() > (long long)anss2.length())
    cout << anss1 << endl;
  else
    cout << anss2 << endl;
  return 0;
}
int main() {
  if (fopen("locin.txt", "r")) freopen("locin.txt", "r", stdin);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long test = 1;
  POW[0] = make_pair(1, 1);
  for (long long i = 1; i < MAXN + 5; i++)
    POW[i] = make_pair((POW[i - 1].first * 29) % Base1,
                       (POW[i - 1].second * 29) % Base2);
  cin >> test;
  for (long long T = 1; T <= test; T++) {
    Solves();
  }
}
