#include <bits/stdc++.h>
using namespace std;
vector<int> z_function(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}
int main() {
  int t;
  cin >> t;
  for (int tt = 0; tt < t; tt++) {
    string s;
    cin >> s;
    int prefix = 0;
    for (int i = 0; i < s.length() / 2; i++) {
      if (s[i] == s[s.length() - 1 - i]) {
        prefix++;
      } else {
        break;
      }
    }
    string s_rest = s.substr(prefix, s.length() - 2 * prefix);
    string s_rest_reverse = string(s_rest);
    reverse(s_rest_reverse.begin(), s_rest_reverse.end());
    vector<int> z = z_function(s_rest + s_rest_reverse);
    int palindrome_length = 0;
    for (int i = s_rest.length(); i < s_rest.length() * 2; i++) {
      if (z[i] == s_rest.length() * 2 - i) {
        palindrome_length = s_rest.length() * 2 - i;
        break;
      }
    }
    z = z_function(s_rest_reverse + s_rest);
    int palindrome_length_2 = 0;
    for (int i = s_rest.length(); i < s_rest.length() * 2; i++) {
      if (z[i] == s_rest.length() * 2 - i) {
        palindrome_length_2 = s_rest.length() * 2 - i;
        break;
      }
    }
    if (palindrome_length > palindrome_length_2) {
      for (int i = 0; i < prefix + palindrome_length; i++) {
        cout << s[i];
      }
      for (int i = s.length() - prefix; i < s.length(); i++) {
        cout << s[i];
      }
      cout << "\n";
    } else {
      for (int i = 0; i < prefix; i++) cout << s[i];
      for (int i = s.length() - prefix - palindrome_length_2; i < s.length();
           i++)
        cout << s[i];
      cout << "\n";
    }
  }
  return 0;
}
