#include <bits/stdc++.h>
using namespace std;
int R[2000009];
char S[1000009], T[2000009];
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf(" %s", S + 1);
    int N = strlen(S + 1);
    for (int i = 1; i <= 2 * N + 1; i += 2) T[i] = '#';
    for (int i = 2; i <= 2 * N + 1; i += 2) T[i] = S[i / 2];
    int rm = -1, rmi = -1;
    for (int i = 1; i <= 2 * N + 1; i++) {
      if (i <= rm)
        R[i] = min(rm - i, R[2 * rmi - i]);
      else
        R[i] = 0;
      while (i - R[i] - 1 >= 1 && i + R[i] + 1 <= 2 * N + 1 &&
             T[i - R[i] - 1] == T[i + R[i] + 1])
        ++R[i];
      if (rm < i + R[i]) rm = i + R[i], rmi = i;
    }
    int x = 0;
    for (int i = 1; i <= N; i++) {
      if (T[i] == T[2 * N - i + 2])
        ++x;
      else
        break;
    }
    int am = -1, ar = -1;
    for (int i = x + 1; i <= 2 * N - x + 1; i++) {
      int r = min({R[i], i - x - 1, 2 * N - x + 1 - i});
      if (x + 1 == i - r || i + r == 2 * N - x + 1) {
        if (ar < r) am = i, ar = r;
      }
    }
    for (int i = 2; i <= 2 * N + 1; i += 2) {
      if (i <= x || (am - ar <= i && i <= am + ar) || 2 * N - x + 2 <= i)
        printf("%c", T[i]);
    }
    puts("");
  }
  return 0;
}
