#include <bits/stdc++.h>
using namespace std;
long long spf[1000005];
vector<long long> primes, prev[1000005], next[1000005];
void sieve() {
  for (long long i = 2; i < 1000005; ++i) {
    if (spf[i] == 0) {
      spf[i] = i;
      for (long long j = 2 * i; j <= 1000005; j += i) {
        if (spf[j] == 0) spf[j] = i;
      }
    }
  }
}
bool cmp(const pair<long long, long long>& a,
         const pair<long long, long long>& b) {
  if (a.first == b.first)
    return a.second < b.second;
  else
    return a.first > b.first;
}
string kmp(string s) {
  long long n = s.size();
  vector<long long> p(n);
  long long i = 1, len = 0;
  while (i < n) {
    if (s[i] == s[len]) {
      len++;
      p[i] = len;
      i++;
    } else {
      if (len != 0) {
        len = p[len - 1];
      } else {
        p[i] = 0;
        i++;
      }
    }
  }
  long long ans = p[n - 1];
  string t = s.substr(0, ans);
  return t;
}
string pal(string t) {
  string r = t;
  reverse(r.begin(), r.end());
  string t1 = kmp(r + "#" + t);
  string t2 = kmp(t + "#" + r);
  return t1.size() > t2.size() ? t1 : t2;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  srand(static_cast<unsigned>(time(0)));
  long long t = 1;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    long long n = s.size();
    long long i = 0;
    while (i <= n - i - 1 && s[i] == s[n - i - 1]) {
      i++;
    }
    if (i > n - i - 1) {
      cout << s << "\n";
      continue;
    }
    string t1 = s.substr(i, n - 2 * i);
    string ans = pal(t1);
    string temp = s.substr(0, i);
    ans = temp + ans;
    reverse(temp.begin(), temp.end());
    ans = ans + temp;
    cout << ans << "\n";
  }
  return 0;
}
