#include <bits/stdc++.h>
using namespace std;
bool is(long long l, long long r, string& s) {
  for (long long i = l; i < l + (r - l) / 2; i++) {
    if (s[i] != s[r + l - i - 1]) {
      return 0;
    }
  }
  return 1;
}
vector<long long> v = {31, 73, 239, 43},
                  u = {1000000007, 998244353, 1000000009};
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t;
  mt19937 rnd(11);
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    string ans;
    long long n = s.size();
    for (long long i = 0; i < n / 2 + 1; i++) {
      if (i == n / 2) {
        cout << s;
        break;
      }
      if (s[i] == s[n - 1 - i]) {
        ans += s[i];
      } else {
        long long p = v[abs((long long)rnd()) % 4],
                  mod = u[abs((long long)rnd()) % 3];
        vector<long long> dg(s.size() + 1, 1);
        for (long long j = 0; j < (long long)s.size(); j++) {
          dg[j + 1] = dg[j] * p % mod;
        }
        cout << ans;
        long long mx = 0, mx1 = 0;
        long long h = 0, hr = 0;
        for (long long j = i; j < n - i; j++) {
          h = (h + (s[j] - 'a') * dg[j - i]) % mod;
          hr = (hr * p + (s[j] - 'a')) % mod;
          if (h == hr) {
            mx = j + 1 - i;
          }
        }
        h = 0;
        hr = 0;
        for (long long j = n - i - 1; j >= i; j--) {
          h = (h + (s[j] - 'a') * dg[n - i - 1 - j]) % mod;
          hr = (hr * p + (s[j] - 'a')) % mod;
          if (h == hr) {
            mx1 = n - i - j;
          }
        }
        if (mx1 > mx) {
          for (long long j = n - i - mx1; j < n - i; j++) {
            cout << s[j];
          }
        } else {
          for (long long j = i; j < i + mx; j++) {
            cout << s[j];
          }
        }
        for (long long j = 0; j < ans.size(); j++) {
          cout << ans[ans.size() - 1 - j];
        }
        break;
      }
    }
    cout << '\n';
  }
  return 0;
}
