#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const double EPS = 1e-8;
const long double EUL = 2.71828182845904523536;
const long double PII = 3.14159265358979323846;
string longestprefixpalindrome(string s) {
  string t = s + '#';
  reverse((t).begin(), (t).end());
  t = s + t;
  int n = t.size();
  vector<int> lps(n + 1);
  for (int i = 1; i <= n; i++) {
    int len = lps[i - 1];
    while (len && t[len] != t[i]) len = lps[len - 1];
    if (t[len] == t[i]) len++;
    lps[i] = len;
  }
  return t.substr(0, lps[n - 1]);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int n = s.size();
    int l = 0;
    while (l < n / 2 && s[l] == s[n - l - 1]) l++;
    string t = s.substr(l, n - 2 * l);
    string x1 = longestprefixpalindrome(t);
    reverse((t).begin(), (t).end());
    string x2 = longestprefixpalindrome(t);
    string extra = (x1.size() > x2.size() ? x1 : x2);
    string ans = s.substr(0, l) + extra + s.substr(n - l, l);
    cout << ans << endl;
  }
  cerr << "Time : " << 1000 * (long double)clock() / (long double)CLOCKS_PER_SEC
       << "ms\n";
  return 0;
}
