#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
using ii = pair<long long int, long long int>;
class prioritize {
 public:
  bool operator()(ii &p1, ii &p2) { return p1.first < p2.first; }
};
auto start_time = high_resolution_clock::now();
void time() { return; }
void ojudge() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  return;
}
long long int pref_lps(string s4) {
  long long int nnn = (long long int)s4.size();
  vector<long long int> lps(nnn, 0);
  for (long long int i = 1; i < nnn; i++) {
    long long int j = lps[i - 1];
    while (j > 0 && s4[i] != s4[j]) j = lps[j - 1];
    if (s4[j] == s4[i]) j++;
    lps[i] = j;
  }
  long long int req_len = lps[nnn - 1];
  return req_len;
}
int main() {
  ojudge();
  long long int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    long long int n = (long long int)s.size();
    if (n == 1) {
      cout << s << "\n";
      continue;
    }
    string a = "", b = "";
    long long int lo = 0, hi = n - 1;
    while (s[lo] == s[hi] && (lo < hi)) {
      a.push_back(s[lo]);
      b.push_back(s[hi]);
      lo++;
      hi--;
    }
    reverse((b).begin(), (b).end());
    if (((long long int)a.size() + (long long int)b.size()) == n)
      cout << a << b << "\n";
    else {
      string s2 =
          s.substr(lo, n - ((long long int)a.size() + (long long int)b.size()));
      string s3 = s2;
      reverse((s3).begin(), (s3).end());
      string s4 = s2 + '#' + s3;
      long long int req_f = pref_lps(s4);
      string s5 = s3 + '#' + s2;
      long long int req_bk = pref_lps(s5);
      if (req_f >= req_bk)
        cout << a << s4.substr(0, req_f) << b << "\n";
      else
        cout << a << s5.substr(0, req_bk) << b << "\n";
    }
  }
  time();
  return 0;
}
