#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B, typename C>
struct triple {
  A X;
  B Y;
  C Z;
  triple(A a = 0, B b = 0, C c = 0) : X(a), Y(b), Z(c) {}
};
template <typename A, typename B, typename C>
triple<A, B, C> make_triple(A a = 0, B b = 0, C c = 0) {
  return triple<A, B, C>(a, b, c);
}
template <typename A, typename B, typename C>
bool operator<(const triple<A, B, C>& a, const triple<A, B, C>& b) {
  if (a.X != b.X) return a.X < b.X;
  if (a.Y != b.Y) return a.Y < b.Y;
  return a.Z < b.Z;
}
template <typename T, typename SS>
ostream& operator<<(ostream& ofs, const pair<T, SS>& p) {
  ofs << "( " << p.first << " , " << p.second << " )";
  return ofs;
}
template <typename T>
void print(T a) {
  for (auto i : a) cout << i << ' ';
  cout << '\n';
}
template <typename T>
T max(T a, T b, T c) {
  return max(a, max(b, c));
}
template <typename T>
T min(T a, T b, T c) {
  return min(a, min(b, c));
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
long long gen_base(const long long before, const long long after) {
  auto seed =
      std::chrono::high_resolution_clock::now().time_since_epoch().count();
  std::mt19937 mt_rand(seed);
  long long base =
      std::uniform_int_distribution<long long>(before + 1, after)(mt_rand);
  return base % 2 == 0 ? base - 1 : base;
}
struct PolyHash {
  static const long long mod = (long long)1e9 + 123;
  static std::vector<long long> pow1;
  static std::vector<unsigned long long> pow2;
  static long long base;
  static inline long long diff(long long a, long long b) {
    return (a -= b) < 0 ? a + mod : a;
  }
  std::vector<long long> pref1;
  std::vector<unsigned long long> pref2;
  PolyHash(const std::string& s)
      : pref1(s.size() + 1u, 0), pref2(s.size() + 1u, 0) {
    const long long n = s.size();
    while ((long long)pow1.size() <= n) {
      pow1.push_back(1LL * pow1.back() * base % mod);
      pow2.push_back(pow2.back() * base);
    }
    for (long long i = 0; i < n; ++i) {
      pref1[i + 1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
      pref2[i + 1] = pref2[i] + s[i] * pow2[i];
    }
  }
  inline std::pair<long long, unsigned long long> operator()(
      const long long pos, const long long len,
      const long long mxPow = 0) const {
    long long hash1 = pref1[pos + len] - pref1[pos];
    unsigned long long hash2 = pref2[pos + len] - pref2[pos];
    if (hash1 < 0) hash1 += mod;
    if (mxPow != 0) {
      hash1 = 1LL * hash1 * pow1[mxPow - (pos + len - 1)] % mod;
      hash2 *= pow2[mxPow - (pos + len - 1)];
    }
    return std::make_pair(hash1, hash2);
  }
};
long long PolyHash::base((long long)1e9 + 7);
std::vector<long long> PolyHash::pow1{1};
std::vector<unsigned long long> PolyHash::pow2{1};
signed main() {
  srand(time(NULL));
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);
  PolyHash::base = gen_base(256, PolyHash::mod);
  long long t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    long long n = s.size();
    string a = s;
    string b = "";
    reverse_copy(s.begin(), s.end(), back_inserter(b));
    string ans;
    long long i = 0;
    while (i < n && a[i] == b[i]) ans.push_back(a[i++]);
    if (i == n) {
      cout << ans << '\n';
      continue;
    }
    auto fnd = [](string s) {
      long long n = (long long)(s.size());
      string rs;
      reverse_copy(s.begin(), s.end(), back_inserter(rs));
      const long long mxPow = n;
      PolyHash a(s), b(rs);
      auto good = [&](long long x, long long ln) {
        long long y = x + ln - 1;
        return a(x, ln, mxPow) == b(n - y - 1, ln, mxPow);
      };
      long long p1, p2;
      p1 = p2 = -1;
      for (long long i = 0; i + i < n; i++) {
        if (good(0, 2 * i + 1)) p1 = 2 * i + 1;
      }
      for (long long i = 0; 2 * i + 1 < n; i++) {
        if (good(0, 2 * i + 2)) p2 = 2 * i + 2;
      }
      return (p1 > p2) ? s.substr(0, p1) : s.substr(0, p2);
    };
    string c;
    for (long long j = i; j < n - i; j++) c.push_back(a[j]);
    string x = fnd(c);
    reverse(c.begin(), c.end());
    string y = fnd(c);
    string z = ((long long)(x.size()) > (long long)(y.size()) ? x : y);
    cout << ans << z;
    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
  }
}
