#include <bits/stdc++.h>
using namespace std;
vector<long long int> A;
vector<unsigned long long int> B;
vector<long long int> C;
vector<unsigned long long int> D;
unsigned long long int exp(unsigned long long int a, long long int b) {
  if (b == 0) return 1;
  if (b % 2) return a * exp(a, b - 1);
  long long int t = exp(a, b / 2);
  return t * t;
}
long long int exp(long long int a, long long int b, long long int m) {
  if (b == 0) return 1;
  if (b % 2) return a * exp(a, b - 1, m) % m;
  long long int t = exp(a, b / 2, m);
  return t * t % m;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int q;
  cin >> q;
  while (q--) {
    string s;
    cin >> s;
    reverse((s).begin(), (s).end());
    s += "$";
    reverse((s).begin(), (s).end());
    long long int n = ((long long int)(s).size()) - 1;
    long long int a = 1, b = n;
    A = C = vector<long long int>(n + 2, 0);
    B = D = vector<unsigned long long int>(n + 2, 0);
    for (long long int i = 1; i <= n; i++) {
      A[i] = (A[i - 1] * 37ll + (s[i] - 'a' + 1)) % 1000000007;
      B[i] = B[i - 1] * 43ull + (s[i] - 'a' + 1);
    }
    for (long long int i = n; i >= 1; i--) {
      C[i] = (C[i + 1] * 37ll + (s[i] - 'a' + 1)) % 1000000007;
      D[i] = D[i + 1] * 43ull + (s[i] - 'a' + 1);
    }
    while (a < b && s[a] == s[b]) {
      a++;
      b--;
    }
    a--, b++;
    long long int l = min(b - 1, a + 1);
    for (long long int d = 1; 1; d++) {
      long long int L = a + 1;
      long long int lm = L + d - 1;
      long long int rm = lm + 1;
      long long int R = rm + d - 1;
      if (R >= b) break;
      long long int h1 =
          (A[lm] - A[L - 1] * exp(37, d, 1000000007) % 1000000007 +
           1000000007) %
          1000000007;
      unsigned long long int h2 = B[lm] - B[L - 1] * exp(43, d);
      long long int h3 =
          (C[rm] - C[R + 1] * exp(37, d, 1000000007) % 1000000007 +
           1000000007) %
          1000000007;
      unsigned long long int h4 = D[rm] - D[R + 1] * exp(43, d);
      if (h1 == h3 && h2 == h4) l = max(l, R);
    }
    for (long long int d = 1; 1; d++) {
      long long int L = a + 1;
      long long int lm = L + d - 1;
      long long int rm = lm + 2;
      long long int R = rm + d - 1;
      if (R >= b) break;
      long long int h1 =
          (A[lm] - A[L - 1] * exp(37, d, 1000000007) % 1000000007 +
           1000000007) %
          1000000007;
      unsigned long long int h2 = B[lm] - B[L - 1] * exp(43, d);
      long long int h3 =
          (C[rm] - C[R + 1] * exp(37, d, 1000000007) % 1000000007 +
           1000000007) %
          1000000007;
      unsigned long long int h4 = D[rm] - D[R + 1] * exp(43, d);
      if (h1 == h3 && h2 == h4) l = max(l, R);
    }
    long long int r = max(a + 1, b - 1);
    for (long long int d = 1; 1; d++) {
      long long int R = b - 1;
      long long int rm = R - d + 1;
      long long int lm = rm - 1;
      long long int L = lm - d + 1;
      if (L <= a) break;
      long long int h1 =
          (A[lm] - A[L - 1] * exp(37, d, 1000000007) % 1000000007 +
           1000000007) %
          1000000007;
      unsigned long long int h2 = B[lm] - B[L - 1] * exp(43, d);
      long long int h3 =
          (C[rm] - C[R + 1] * exp(37, d, 1000000007) % 1000000007 +
           1000000007) %
          1000000007;
      unsigned long long int h4 = D[rm] - D[R + 1] * exp(43, d);
      if (h1 == h3 && h2 == h4) r = min(r, L);
    }
    for (long long int d = 1; 1; d++) {
      long long int R = b - 1;
      long long int rm = R - d + 1;
      long long int lm = rm - 2;
      long long int L = lm - d + 1;
      if (L <= a) break;
      long long int h1 =
          (A[lm] - A[L - 1] * exp(37, d, 1000000007) % 1000000007 +
           1000000007) %
          1000000007;
      unsigned long long int h2 = B[lm] - B[L - 1] * exp(43, d);
      long long int h3 =
          (C[rm] - C[R + 1] * exp(37, d, 1000000007) % 1000000007 +
           1000000007) %
          1000000007;
      unsigned long long int h4 = D[rm] - D[R + 1] * exp(43, d);
      if (h1 == h3 && h2 == h4) r = min(r, L);
    }
    if (l - a >= b - r) {
      for (long long int i = 1; i <= l; i++) cout << s[i];
      for (long long int i = b; i <= n; i++) cout << s[i];
    } else {
      for (long long int i = 1; i <= a; i++) cout << s[i];
      for (long long int i = r; i <= n; i++) cout << s[i];
    }
    cout << '\n';
  }
}
