#include <bits/stdc++.h>
#pragma GCC optimize "trapv"
const int inf1 = 1e9;
const long long int inf2 = 1e18;
const int N = 100000;
using namespace std;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<int> z_function(string s) {
  int n = 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;
}
bool ispalindrome(string s) {
  string t = s;
  reverse(s.begin(), s.end());
  return t == s;
}
string LPP(string s) {
  if (s.length() == 1) return s;
  int l = s.length();
  string t = s + "#";
  string t2 = s;
  reverse(t2.begin(), t2.end());
  t += t2;
  vector<int> z = z_function(t);
  int l2 = 2 * l + 1;
  for (int i = l + 1; i < l2; i++) {
    if (z[i] == (l2 - i)) {
      string ans = t.substr(i, l2 - i);
      return ans;
    }
  }
}
int solve() {
  string s;
  cin >> s;
  int n = s.length();
  if (ispalindrome(s)) {
    cout << s << "\n";
    return 0;
  }
  int i = 0;
  while (s[i] == s[n - 1 - i]) i++;
  string ans = s.substr(0, i);
  string ans4 = ans;
  reverse(ans4.begin(), ans4.end());
  string s2 = s.substr(i, n - 2 * i);
  string s3 = s2;
  reverse(s3.begin(), s3.end());
  string ans1 = LPP(s2);
  string ans2 = LPP(s3);
  if (ans1.size() >= ans2.size()) {
    cout << ans + ans1 + ans4 << "\n";
  } else {
    cout << ans + ans2 + ans4 << "\n";
  }
  return 0;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
