#include <bits/stdc++.h>
using namespace std;
vector<int> manacher(string s) {
  string T = "#";
  for (char c : s) T += c, T += '#';
  vector<int> P((T).size());
  int c = 0, r = 0;
  for (auto(i) = (1); (i) < ((T).size() + 1); ++(i)) {
    if (r > i) {
      P[i] = min(r - i, P[2 * c - i]);
    }
    while (i + 1 + P[i] < (T).size() && i - 1 - P[i] >= 0 &&
           T[i + 1 + P[i]] == T[i - 1 - P[i]]) {
      P[i]++;
    }
    if (i + P[i] > r) {
      c = i;
      r = i + P[i];
    }
  }
  return P;
}
void solve() {
  string s;
  cin >> s;
  int l = 0;
  int r = (s).size() - 1;
  string res1 = "";
  while (r - 1 > l + 1 && s[r] == s[l]) {
    res1 += s[r];
    r--;
    l++;
  }
  string s2(s, l, r - l + 1);
  vector<int> P = manacher(s2);
  int maxLenL = 0;
  for (auto(i) = (1); (i) < ((P).size() - 1); ++(i))
    if (P[i] == i) maxLenL = i;
  int maxLenR = 0;
  for (auto(i) = ((P).size() - 2); (i) > (1); --(i))
    if (P[i] == (P).size() - i - 1) maxLenR = (P).size() - i - 1;
  cout << res1
       << (maxLenL > maxLenR ? string(s2, 0, maxLenL)
                             : string(s2, (s2).size() - maxLenR, maxLenR))
       << string((res1).rbegin(), (res1).rend()) << '\n';
}
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  int tc;
  cin >> tc;
  while (tc--) solve();
}
