#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  string tmp;
  for (int req = 0; req < t; ++req) {
    cin >> tmp;
    string str;
    int cnt = -1;
    int n = tmp.size();
    for (int i = 0; i < n / 2; ++i) {
      if (tmp[i] != tmp[n - i - 1]) {
        cnt = i;
        break;
      }
    }
    if (cnt == -1) {
      cnt = n / 2;
    }
    str = "#";
    for (int i = 0; i < n; ++i) {
      str += tmp[i];
      str += "#";
    }
    n = str.size();
    int s = 2 * cnt;
    int f = n - 2 * cnt;
    vector<int> z(n);
    int m = 0;
    int r = 0;
    for (int i = 0; i < n; i += 2) {
      z[i] = max(0, min(r - (i - m), z[m - (i - m)]));
      while (i - z[i] >= 0 && i + z[i] < n && str[i - z[i]] == str[i + z[i]]) {
        ++z[i];
      }
      if (m + r < i + z[i]) {
        m = i;
        r = z[i];
      }
    }
    m = 0;
    r = 0;
    for (int i = 1; i < n; i += 2) {
      z[i] = max(0, min(r - (i - m), z[m - (i - m)]));
      while (i - z[i] >= 0 && i + z[i] < n && str[i - z[i]] == str[i + z[i]]) {
        ++z[i];
      }
      if (m + r < i + z[i]) {
        m = i;
        r = z[i];
      }
    }
    int ind = 0;
    for (int i = s; i < f; ++i) {
      if (i - z[i] + 1 <= s || i + z[i] >= f) {
        int ch1 = min(ind - s + 1, f - ind);
        if (ind % 2 == 1) {
          ch1 = ch1 - 1;
        } else {
          ch1 = ch1 / 2 * 2;
        }
        int ch2 = min(i - s + 1, f - i);
        if (i % 2 == 1) {
          ch2 = ch2 - 1;
        } else {
          ch2 = ch2 / 2 * 2;
        }
        if (ch1 < ch2) {
          ind = i;
        }
      }
    }
    for (int i = 0; i < cnt; ++i) {
      cout << str[2 * i + 1];
    }
    int ch1 = max(ind - z[ind] + 1, s);
    int ch2 = min(ind + z[ind], f);
    int tmp = min(ind - ch1, ch2 - (ind + 1));
    for (int i = ind - tmp; i < ind + tmp; ++i) {
      if (str[i] != '#') {
        cout << str[i];
      }
    }
    for (int i = cnt - 1; i >= 0; --i) {
      cout << str[n - 2 * i - 2];
    }
    cout << "\n";
  }
  return 0;
}
