#include <bits/stdc++.h>
using namespace std;
const int N = int(2e6) + 12, mod = int(1e9) + 7;
int n, z[N];
char second[N];
int Z(string x) {
  int m = int(x.size());
  string t = x;
  reverse((t).begin(), (t).end());
  string second = x + "#" + t;
  int res = 0;
  for (int i = 1, l = 0, r = 0; i < second.size(); i++) {
    z[i] = 0;
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < second.size() && second[z[i]] == second[i + z[i]]) z[i]++;
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    if (i > m && i + z[i] == int(second.size())) {
      res = max(res, z[i]);
    }
  }
  return res;
}
void solve() {
  scanf("\n%s", second + 1);
  n = strlen(second + 1);
  int l = 1, r = n;
  while (l <= r) {
    if (second[l] == second[r]) {
      l++;
      r--;
    } else
      break;
  }
  string a = "";
  for (int i = l; i <= r; i++) {
    a += second[i];
  }
  string b = a;
  string ans = "";
  reverse((b).begin(), (b).end());
  int z1 = Z(a);
  int z2 = Z(b);
  for (int i = 1; i < l; i++) ans += second[i];
  if (z1 > z2) {
    for (int i = 0; i < z1; i++) ans += a[i];
  } else {
    for (int i = 0; i < z2; i++) ans += b[i];
  }
  for (int i = max(r + 1, l); i <= n; i++) ans += second[i];
  for (int i = 0; i < ans.size(); i++) {
    putchar(ans[i]);
  }
  puts("");
}
int main() {
  int T = 1;
  scanf("%d", &T);
  while (T--) {
    solve();
  }
  return 0;
}
