#include <bits/stdc++.h>
#pragma comment(linker, "/stack:512000000")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 gen(time(NULL));
ll const mod = 998244353;
namespace {
ll mul(ll a, ll b) {
  ll val = a * b - (ll)((ld)a * b / mod) * mod;
  if (val < 0) val += mod;
  if (val >= mod) val -= mod;
  return val;
}
ll poww(ll a, ll b) {
  ll val = 1;
  a %= mod;
  while (b > 0) {
    if (b % 2) val = mul(a, val);
    a = mul(a, a);
    b >>= 1;
  }
  return val % mod;
}
ll inv(ll a) { return poww(a, mod - 2); }
}  // namespace
int const maxn = 3e5 + 5;
string go(string s) {
  string s1 = s;
  reverse(s1.begin(), s1.end());
  if (s1 == s) {
    return s;
  }
  int n = s.size();
  vector<vector<int>> p(2, vector<int>(n, 0));
  for (int z = 0, l = 0, r = 0; z < 2; z++, l = 0, r = 0)
    for (int i = 0; i < n; i++) {
      if (i < r) p[z][i] = min(r - i + !z, p[z][l + r - i + !z]);
      int L = i - p[z][i], R = i + p[z][i] - !z;
      while (L - 1 >= 0 && R + 1 < n && s[L - 1] == s[R + 1])
        p[z][i]++, L--, R++;
      if (R > r) l = L, r = R;
    }
  int b = n / 2;
  int j = n - 1;
  string ans = "";
  int mx = 0;
  for (int i = 0; i < b; i++) {
    if (s[i] != s[j]) break;
    mx++;
    j--;
  }
  int nechet_ans = -1;
  int nechet_sz = -1;
  for (int i = 0; i < b; i++) {
    int kek = p[1][i];
    int j = i - kek - 1;
    if (j < mx) {
      j = mx - 1;
      int sz = 2 * (j + 1) + (i - j) * 2 - 1;
      if (sz > nechet_sz) {
        nechet_ans = i;
        nechet_sz = sz;
      }
    }
  }
  if (nechet_sz != -1) {
    int i = nechet_ans;
    int j = mx - 1;
    string roflan = "";
    for (int jj = 0; jj < i; jj++) {
      roflan += s[jj];
    }
    string roflan1 = roflan;
    reverse(roflan1.begin(), roflan1.end());
    roflan = roflan + s[i] + roflan1;
    ans = roflan;
  }
  int chet_ans = -1;
  int chet_sz = -1;
  for (int i = 0; i <= b; i++) {
    int kek = p[0][i];
    int j = i - kek - 1;
    if (j < mx) {
      j = mx - 1;
      int sz = 2 * (j + 1) + (i - j - 1) * 2;
      if (sz > chet_sz) {
        chet_sz = sz;
        chet_ans = i;
      }
    }
  }
  if (chet_sz != -1 && chet_sz > nechet_sz) {
    int i = chet_ans;
    string roflan = "";
    for (int jj = 0; jj < i; jj++) {
      roflan += s[jj];
    }
    string roflan1 = roflan;
    reverse(roflan1.begin(), roflan1.end());
    roflan = roflan + roflan1;
    ans = roflan;
  }
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int q;
  cin >> q;
  while (q--) {
    string s;
    cin >> s;
    int n = s.size();
    string ss = s;
    reverse(ss.begin(), ss.end());
    string ans1 = go(s);
    string ans2 = go(ss);
    if (ans1.size() > ans2.size()) {
      cout << ans1 << '\n';
    } else {
      cout << ans2 << '\n';
    }
  }
  return 0;
}
