#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 7;
string pat;
int F[N];
int getNewLen(int len, char c) {
  while (len && c != pat[len]) len = F[len - 1];
  return len + (c == pat[len]);
}
void computeF() {
  F[0] = 0;
  for (int i = 1; pat[i]; i++) F[i] = getNewLen(F[i - 1], pat[i]);
}
string solve(string &s) {
  int n = s.size();
  int j = 0;
  while (s[j] == s[n - 1 - j] && j < n / 2) j++;
  pat = s.substr(j, n - 2 * j);
  reverse(pat.begin(), pat.end());
  pat = s.substr(j, n - 2 * j) + "|" + pat;
  computeF();
  string cpy = s.substr(0, j);
  reverse(cpy.begin(), cpy.end());
  string ans = s.substr(0, j) + pat.substr(0, F[pat.size() - 1]) + cpy;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  for (int i = 0; i < t; ++i) {
    string s;
    cin >> s;
    string op1 = solve(s);
    reverse(s.begin(), s.end());
    string op2 = solve(s);
    if (op1.size() > op2.size())
      cout << op1 << '\n';
    else
      cout << op2 << '\n';
  }
}
