#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int prod(int a, int b) { return (1LL * a * b) % mod; }
int sum(int a, int b) { return (a + b) % mod; }
int putlog(int n, int k) {
  if (k == 0) return 1;
  if (k == 1) return n;
  int x = putlog(n, k / 2);
  if (k % 2 == 0)
    return prod(x, x);
  else
    return prod(prod(x, x), n);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string s, ns = "";
    cin >> s;
    int i = 0;
    while (i < s.size() and s[i] == s[s.size() - i - 1]) i++;
    if (i == s.size()) {
      cout << s << "\n";
      continue;
    }
    for (int j = i; j <= s.size() - i - 1; j++) ns += s[j];
    int dir = 0;
    int msk1 = 0, msk2 = 0, ans = -1;
    for (int j = 0; j < ns.size(); j++) {
      msk1 = sum(prod(msk1, 27), (ns[j] - 'a'));
      msk2 = sum(msk2, prod(ns[j] - 'a', putlog(27, j)));
      if (msk1 == msk2) ans = j, dir = 1;
    }
    msk1 = 0, msk2 = 0;
    for (int j = ns.size() - 1; j >= 0; j--) {
      msk1 = sum(prod(msk1, 27), (ns[j] - 'a'));
      msk2 = sum(msk2, prod(ns[j] - 'a', putlog(27, ns.size() - j - 1)));
      if (msk1 == msk2)
        if ((ns.size() - j) > ans) ans = (ns.size() - j), dir = 2;
    }
    for (int j = 0; j < i; j++) cout << s[j];
    if (dir == 1)
      for (int j = 0; j <= ans; j++) cout << ns[j];
    else
      for (int j = ns.size() - 1; j >= ns.size() - ans; j--) cout << ns[j];
    for (int j = i - 1; j >= 0; j--) cout << s[j];
    cout << "\n";
  }
}
