#include <bits/stdc++.h>
using namespace std;
const int divider = INT_MAX;
const int power = 31;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  string s1, s, res;
  bool reversed;
  int i, ans;
  while (t--) {
    ans = 0;
    res = "";
    cin >> s;
    i = 0;
    while (s[i] == s[s.size() - 1 - i] && i < s.size() - 1 - i) i++;
    res = s.substr(0, i);
    s = s.substr(i, s.size() - 2 * i);
    long long h1, h2, p;
    for (int i = 0; i < 2; i++) {
      h1 = 0, h2 = 0, p = 1;
      for (int j = 0; j < s.size(); j++) {
        h1 += s[j] * p;
        h1 = h1 % divider;
        h2 *= power;
        h2 += s[j];
        h2 = h2 % divider;
        p *= power;
        p = p % divider;
        if (h1 == h2 && ans < j + 1) {
          ans = j + 1;
          reversed = i;
        }
      }
      if (i == 0) reverse(s.begin(), s.end());
    }
    s1 = res;
    reverse(s1.begin(), s1.end());
    if (!reversed) reverse(s.begin(), s.end());
    cout << res << s.substr(0, ans) << s1 << endl;
  }
  return 0;
}
