#include <bits/stdc++.h>
using namespace std;
const long long int maxn = 201001;
vector<long long int> z_func(string s) {
  long long int n = (long long int)(s.length());
  vector<long long int> z(n);
  for (long long 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;
}
signed main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  long long int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    string ans = "";
    long long int l = 0, r = s.size() - 1;
    while (l <= r) {
      if (s[l] != s[r]) {
        break;
      }
      ans.push_back(s[l]);
      l++;
      r--;
    }
    if (l > r) {
      if (l - r > 1) {
        r++;
      }
      for (long long int d = r + 1; d < s.size(); d++) {
        ans.push_back(s[d]);
      }
      cout << s << "\n";
      continue;
    }
    string ans1 = "", s1 = "";
    string s11 = "";
    for (long long int d = l; d <= r; d++) {
      s1.push_back(s[d]);
      s11.push_back(s[d]);
    }
    s11.push_back('#');
    for (long long int d = s1.size() - 1; d >= 0; d--) {
      s11.push_back(s1[d]);
    }
    vector<long long int> z = z_func(s11);
    long long int max1 = 0;
    for (long long int len = 1; len <= s1.size(); len++) {
      if (z[s11.size() - len] >= len) {
        max1 = len;
      }
    }
    long long int max2 = 0;
    s11 = "";
    for (long long int d = s1.size() - 1; d >= 0; d--) {
      s11.push_back(s1[d]);
    }
    s11.push_back('#');
    for (long long int d = 0; d < s1.size(); d++) {
      s11.push_back(s1[d]);
    }
    z = z_func(s11);
    for (long long int len = 1; len <= s1.size(); len++) {
      if (z[s11.size() - len] >= len) {
        max2 = len;
      }
    }
    for (long long int d = 0; d < l; d++) {
      ans1.push_back(s[d]);
    }
    if (max1 >= max2) {
      for (long long int d = 0; d < max1; d++) {
        ans1.push_back(s1[d]);
      }
    } else {
      for (long long int d = 0; d < max2; d++) {
        ans1.push_back(s11[d]);
      }
    }
    for (long long int d = r + 1; d < s.size(); d++) {
      ans1.push_back(s[d]);
    }
    cout << ans1 << "\n";
  }
}
