#include <bits/stdc++.h>
using namespace std;
long long int power(long long int x, long long int y) {
  if (y == 0) return 1;
  long long int temp = power(x, y / 2);
  temp = (temp * temp) % 1000000007;
  if (y % 2) {
    return (temp * x) % 1000000007;
  }
  return temp;
}
long long int modinv(long long int x) { return power(x, 1000000007 - 2); }
int lps[1000005];
int rps[1000005];
int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t;
  cin >> t;
  ;
  while (t--) {
    string s;
    cin >> s;
    ;
    string pre = "", suf = "";
    long long int i = 0, j = s.length() - 1;
    while (s[i] == s[j] && i < j) {
      i++;
      j--;
    }
    pre = s.substr(0, i);
    suf = s.substr(j + 1, s.length());
    for (int v = 0; v < s.length(); v++) lps[v] = -1;
    for (int p = i + 1; p < j + 1; p++) {
      if (lps[p - 1] == -1) {
        if (s[p] == s[i])
          lps[p] = i;
        else
          lps[p] = -1;
      } else {
        if (s[p] == s[lps[p - 1] + 1])
          lps[p] = lps[p - 1] + 1;
        else if (s[p] == s[i])
          lps[p] = i;
        else
          lps[p] = -1;
      }
    }
    for (int v = 0; v < s.length(); v++) rps[v] = -1;
    for (int p = j - 1; p >= 0; p--) {
      if (p < i) break;
      if (rps[p + 1] == -1) {
        if (s[p] == s[j])
          rps[p] = j;
        else
          rps[p] = -1;
      } else {
        if (s[p] == s[rps[p + 1] - 1])
          rps[p] = rps[p + 1] - 1;
        else if (s[p] == s[j])
          rps[p] = j;
        else
          rps[p] = -1;
      }
    }
    long long int k = i, l = j;
    while (i >= k && j <= l && i < j) {
      if (s[i] == s[j]) {
        i++;
        j--;
      } else {
        if (i == k || lps[i - 1] == -1) {
          i = k;
          if (s[i] != s[j]) j--;
        } else
          i = lps[i - 1] + 1;
      }
    }
    string left;
    if (i == j) {
      left = s.substr(k, 2 * (i - k) + 1);
    } else {
      left = s.substr(k, 2 * (i - k));
    }
    i = k, j = l;
    while (i >= k && j <= l && i < j) {
      if (s[i] == s[j]) {
        i++;
        j--;
      } else {
        if (j == l || rps[j + 1] == -1) {
          j = l;
          if (s[i] != s[j]) i++;
        } else
          j = rps[j + 1] - 1;
      }
    }
    string right;
    if (i == j) {
      right = s.substr(2 * j - l, 2 * (l - j) + 1);
    } else {
      right = s.substr(2 * j - l + 1, 2 * (l - j));
    }
    if (right.length() > left.length())
      cout << pre + right + suf << "\n";
    else
      cout << pre + left + suf << "\n";
  }
}
