#include <bits/stdc++.h>
using namespace std;
void pankajgaur_98() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
long long lps[2000005];
long long get_lps(string& s) {
  long long l = s.length();
  lps[0] = 0;
  long long i = 1, j = 0;
  while (i < l) {
    if (s.at(i) == s.at(j)) {
      lps[i] = j + 1;
      j++;
      i++;
    } else {
      if (j != 0) {
        j = lps[j - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  return lps[s.length() - 1];
}
long long longest_pre_suf(string s) {
  string temp = s + "*";
  reverse(s.begin(), s.end());
  temp += s;
  return get_lps(temp);
}
int32_t main() {
  pankajgaur_98();
  long long t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    long long n = s.length();
    long long cnt = 0;
    long long i = 0;
    long long j = n - 1;
    while (i < j) {
      if (s.at(i) == s.at(j))
        cnt++;
      else
        break;
      i++;
      j--;
    }
    string res = "";
    string b = s.substr(cnt, n - 2 * cnt);
    res += s.substr(0, cnt);
    if (b.size() > 0) {
      long long pref_len = longest_pre_suf(b);
      reverse(b.begin(), b.end());
      long long suf_len = longest_pre_suf(b);
      if (pref_len >= suf_len) {
        reverse(b.begin(), b.end());
        res += b.substr(0, pref_len);
      } else {
        res += b.substr(0, suf_len);
      }
    }
    res += s.substr(n - cnt);
    cout << res << "\n";
  }
  return 0;
}
