#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3", "unroll-loops", "omit-frame-pointer", "inline", \
                     "trapv")
#pragma GCC option("arch=native", "tune=native", "no-zero-upper")
#pragma GCC target("avx")
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const long double PI = acos(-1.0);
void ishan_pandey() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(0);
}
ll power(ll x, ll y) {
  if (y == 0) return 1;
  ll z = power(x, y / 2);
  z = z * z;
  z %= 1000000007;
  return (y & 1 ? (z * x) % 1000000007 : z);
}
bool prime[400005];
ll fac[10000010];
void fact() {
  fac[0] = 1;
  for (long long i = 1; i <= 10000000; i++) {
    fac[i] = (fac[i - 1] * i) % 1000000007;
  }
  return;
}
void sieve() {
  prime[0] = 0;
  prime[1] = 0;
  for (long long i = 2; i < 400005; i++) {
    prime[i] = 1;
  }
  for (long long i = 2; i * i < 400005; i++) {
    if (prime[i] == 1) {
      for (long long j = i * i; j < 400005; j += i) {
        prime[j] = 0;
      }
    }
  }
}
ll siz[500005];
ll par[500005];
ll find(ll u) {
  if (par[u] == u) {
    return u;
  }
  return find(par[u]);
}
void add(ll u, ll v) {
  ll p1 = find(u);
  ll p2 = find(v);
  if (p1 == p2) return;
  if (siz[p1] < siz[p2]) swap(p1, p2);
  siz[p1] += siz[p2];
  par[p2] = p1;
  return;
}
string S;
long long solve1(const string& str) {
  string rev = str;
  reverse(rev.begin(), rev.end());
  string kmps = str + "@" + rev;
  vector<long long> lpsss((long long)kmps.size(), 0);
  for (long long i = 1; i < (long long)lpsss.size(); i++) {
    long long pdx = lpsss[i - 1];
    while (pdx > 0 and kmps[i] != kmps[pdx]) {
      pdx = lpsss[pdx - 1];
    }
    lpsss[i] = pdx + (kmps[i] == kmps[pdx] ? 1 : 0);
  }
  return lpsss[(long long)lpsss.size() - 1];
}
void solve() {
  cin >> S;
  long long left = 0;
  long long right = (long long)S.length() - 1;
  while (left < right) {
    if (S[left] == S[right]) {
      left++;
      right--;
    } else
      break;
  }
  if (left >= right) {
    cout << S << '\n';
    return;
  }
  long long temp1 = 0, temp2 = 0;
  string ansl = "";
  string ansr = "";
  for (long long i = 0; i < left; i++) ansl += S[i];
  for (long long i = right + 1; i < (long long)S.length(); i++) ansr += S[i];
  string temp = "";
  for (long long i = left; i <= right; i++) temp += S[i];
  temp1 = solve1(temp);
  reverse(temp.begin(), temp.end());
  temp2 = solve1(temp);
  if (temp1 > temp2) {
    for (long long i = left; i < left + temp1; i++) ansl += S[i];
  } else {
    for (long long i = right - temp2 + 1; i <= right; i++) ansl += S[i];
  }
  ansl = ansl + ansr;
  cout << ansl << '\n';
}
signed main() {
  ishan_pandey();
  cout << fixed << setprecision(15);
  long long t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
