#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
const int inf = 2e9;
char ma[maxn << 1];
int mp[maxn << 1];
inline void manacher(string &s, int len) {
  int p = 0, r = 0, mid = 0;
  ma[p++] = '$', ma[p++] = '#';
  for (int i = 0; i < len; i++) ma[p++] = s[i], ma[p++] = '#';
  for (int i = 0; i < p; i++) {
    mp[i] = r > i ? min(mp[(mid << 1) - i], r - i) : 1;
    if (i + mp)
      while (ma[i + mp[i]] == ma[i - mp[i]]) mp[i]++;
    if (i + mp[i] > r) r = i + mp[i], mid = i;
  }
}
inline void init(int len) {
  for (int i = 0; i < (len + 1) << 1; i++) {
    mp[i] = 0;
    ma[i] = '*';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int len = s.size();
    int ans = 0;
    for (int i = 0; i < len / 2; i++) {
      if (s[i] == s[len - i - 1])
        ++ans;
      else
        break;
    }
    if (ans == len / 2) {
      cout << s << '\n';
      continue;
    }
    string m = "";
    for (int i = ans; i < len - ans; ++i) m += s[i];
    len = m.size();
    int x = 0, y = 0;
    manacher(m, len);
    for (int i = 0; i < (len + 1) << 1; i++) {
      if (i - mp[i] == 0) x = max(x, mp[i] - 1);
    }
    init(len);
    reverse(m.begin(), m.end());
    manacher(m, len);
    for (int i = 0; i < (len + 1) << 1; i++) {
      if (i - mp[i] == 0) y = max(y, mp[i] - 1);
    }
    init(len);
    for (int i = 0; i < ans; i++) cout << s[i];
    if (x > y) {
      reverse(m.begin(), m.end());
      for (int i = 0; i < x; i++) cout << m[i];
    } else {
      for (int i = 0; i < y; i++) cout << m[i];
    }
    for (int i = ans - 1; i >= 0; --i) cout << s[i];
    cout << '\n';
  }
  return 0;
}
