#include <bits/stdc++.h>
using namespace std;
using db = double;
using ll = long long;
using uint = unsigned int;
using pii = pair<int, int>;
template <class T>
void cmax(T& x, const T& y) {
  if (x < y) x = y;
}
template <class T>
void cmin(T& x, const T& y) {
  if (x > y) x = y;
}
template <class T>
void sort(vector<T>& v) {
  sort(v.begin(), v.end());
}
template <class T>
void reverse(vector<T>& v) {
  reverse(v.begin(), v.end());
}
template <class T>
void unique(vector<T>& v) {
  sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end());
}
const int SZ = 1 << 23 | 233;
struct FILEIN {
  char qwq[SZ], *S = qwq, *T = qwq, ch;
  char GETC() {
    return (S == T) && (T = (S = qwq) + fread(qwq, 1, SZ, stdin), S == T)
               ? EOF
               : *S++;
  }
  FILEIN& operator>>(char& c) {
    while (isspace(c = GETC()))
      ;
    return *this;
  }
  FILEIN& operator>>(string& s) {
    while (isspace(ch = GETC()))
      ;
    s = ch;
    while (!isspace(ch = GETC())) s += ch;
    return *this;
  }
  template <class T>
  void read(T& x) {
    bool sign = 0;
    while ((ch = GETC()) < 48) sign ^= (ch == 45);
    x = (ch ^ 48);
    while ((ch = GETC()) > 47) x = (x << 1) + (x << 3) + (ch ^ 48);
    x = sign ? -x : x;
  }
  FILEIN& operator>>(int& x) { return read(x), *this; }
  FILEIN& operator>>(ll& x) { return read(x), *this; }
} in;
struct FILEOUT {
  const static int LIMIT = 1 << 22;
  char quq[SZ], ST[233];
  int sz, O;
  ~FILEOUT() { flush(); }
  void flush() {
    fwrite(quq, 1, O, stdout);
    fflush(stdout);
    O = 0;
  }
  FILEOUT& operator<<(char c) { return quq[O++] = c, *this; }
  FILEOUT& operator<<(string str) {
    if (O > LIMIT) flush();
    for (char c : str) quq[O++] = c;
    return *this;
  }
  template <class T>
  void write(T x) {
    if (O > LIMIT) flush();
    if (x < 0) {
      quq[O++] = 45;
      x = -x;
    }
    do {
      ST[++sz] = x % 10 ^ 48;
      x /= 10;
    } while (x);
    while (sz) quq[O++] = ST[sz--];
  }
  FILEOUT& operator<<(int x) { return write(x), *this; }
  FILEOUT& operator<<(ll x) { return write(x), *this; }
} out;
const long long maxn = 4e6 + 64;
long long f[maxn], p[maxn];
char s[maxn], t[maxn];
long long n, m, mx, mn, flag;
signed main() {
  long long T;
  scanf("%lld", &T);
  while (T--) {
    scanf("%s", s), m = n = strlen(s);
    t[0] = '$', t[1] = '%';
    for (long long i = 0; i < n; i++) {
      t[i * 2 + 2] = s[i];
      t[i * 2 + 3] = '%';
    }
    t[2 * n + 2] = 0;
    n = strlen(t);
    auto manacher = [&]() {
      long long r = 0, mid;
      for (long long i = 1; i < n; i++) {
        if (i < r) {
          p[i] = min(p[(mid << 1) - i], p[mid] + mid - i);
        } else {
          p[i] = 1;
        }
        while (t[i - p[i]] == t[i + p[i]]) p[i]++;
        if (p[i] + i > r) {
          r = p[i] + i;
          mid = i;
        }
      }
    };
    manacher();
    n--;
    for (register long long i = (1); i <= (n); ++i) f[i] = 0;
    for (register long long i = (1); i <= (n); ++i) p[i]--;
    f[0] = f[n + 1] = 1;
    for (long long i = 1; i <= n; f[i++] = 1)
      if (t[i] != t[n - i + 1]) break;
    auto solve = [&]() {
      mx = 0, mn = 0, flag = 0;
      for (register long long i = (1); i <= (n); ++i) {
        long long l = i - p[i] - 1;
        long long r = n - i - p[i];
        if (f[l] && i + p[i] < n - l + 1) {
          if (i > mx) {
            mx = i - 1;
            mn = i;
            flag = 0;
          }
        }
        if (f[r] && i - p[i] > r) {
          if (n - i > mx) {
            mx = n - i;
            mn = i;
            flag = 1;
          }
        }
      }
    };
    auto print = [&]() {
      if (!flag) {
        for (register long long i = (1); i <= (mn + p[mn]); ++i)
          if (t[i] != '%') out << t[i];
        for (register long long i = (mn - p[mn] - 1); i >= (1); --i)
          if (t[i] != '%') out << t[i];
      } else {
        for (register long long i = (n); i >= (mn - p[mn]); --i)
          if (t[i] != '%') out << t[i];
        for (register long long i = (mn + p[mn] + 1); i <= (n); ++i)
          if (t[i] != '%') out << t[i];
      }
      out << '\n';
    };
    solve();
    print();
  }
  return 0;
}
