#include <bits/stdc++.h>
using namespace std;
vector<int> lps(2000009);
string kmp(string pat) {
  int len = 0;
  int M = pat.size();
  for (int i = 0; i < M; i++) {
    lps[i] = 0;
  }
  lps[0] = 0;
  int i = 1;
  while (i < M) {
    if (pat[i] == pat[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len != 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  int leng = min(lps[M - 1], M / 2);
  return pat.substr(0, leng);
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int l = 0;
    int r = s.size() - 1;
    while (l <= r && s[l] == s[r]) {
      l++;
      r--;
    }
    if (l > r) {
      cout << s << endl;
      continue;
    }
    string ans = s.substr(0, l);
    string rev_ans = ans;
    reverse(rev_ans.begin(), rev_ans.end());
    string temp = s.substr(l, r - l + 1);
    string rev = temp;
    reverse(rev.begin(), rev.end());
    string first = kmp(temp + "*" + rev);
    string second = kmp(rev + "*" + temp);
    if (first.size() >= second.size()) {
      ans += first;
    } else {
      ans += second;
    }
    ans += rev_ans;
    cout << ans << endl;
  }
}
