#include <bits/stdc++.h>
using namespace std;
vector<int> pref(2e6 + 6);
string solve(const string &s) {
  string a = s;
  reverse(a.begin(), a.end());
  a = s + '#' + a;
  int p = 0;
  for (int i = 1; i < (int)a.size(); ++i) {
    while (p != 0 && a[p] != a[i]) p = pref[p - 1];
    if (a[p] == a[i]) ++p;
    pref[i] = p;
  }
  return s.substr(0, p);
}
void test_case() {
  string t;
  cin >> t;
  int l = 0;
  while (l < (int)t.size() - l - 1) {
    if (t[l] != t[(int)t.size() - l - 1]) break;
    ++l;
  }
  cout << t.substr(0, l);
  if ((int)t.size() > 2 * l) {
    string s = t.substr(l, (int)t.size() - 2 * l);
    string a = solve(s);
    reverse(s.begin(), s.end());
    string b = solve(s);
    if ((int)a.size() < (int)b.size()) swap(a, b);
    cout << a;
  }
  cout << t.substr((int)t.size() - l, l) << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int T;
  cin >> T;
  while (T--) test_case();
}
