#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << " " << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
void inp_out() {}
string fun(string s) {
  string temp = s + "#";
  reverse(s.begin(), s.end());
  temp += s;
  long long int n = temp.size();
  s = temp;
  vector<long long int> a(n);
  long long int i = 1, j = 0;
  while (i < n) {
    while ((s[i] != s[j]) && (j != 0)) {
      j = a[j - 1];
    }
    if (s[i] == s[j]) {
      a[i] = j + 1;
      ++j;
    }
    ++i;
  }
  return s.substr(0, a[n - 1]);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  inp_out();
  long long int Testcases;
  cin >> Testcases;
  while (Testcases--) {
    string s;
    cin >> s;
    long long int n = s.size();
    long long int i1 = 0, i2 = n - 1;
    string s1 = "";
    while ((i1 < i2) && (s[i1] == s[i2])) {
      s1 += s[i1];
      ++i1;
      --i2;
    }
    cout << s1;
    long long int s1sz = s1.size();
    string left = s.substr(s1sz, n - 2 * s1sz);
    long long int lsz = left.size();
    long long int mx = 0;
    string s2 = fun(left);
    reverse(left.begin(), left.end());
    string s3 = fun(left);
    reverse(s1.begin(), s1.end());
    cout << (s2.size() > s3.size() ? s2 : s3);
    cout << s1;
    cout << "\n";
  }
  return 0;
}
