#include <bits/stdc++.h>
using namespace std;
string rev(string s) {
  string ret = s;
  reverse(ret.begin(), ret.end());
  return ret;
}
string lpp(string s) {
  int kmp[3 * s.size() + 2];
  memset(kmp, 0, sizeof kmp);
  string now = s + '?' + rev(s);
  for (int i = 1; i <= now.size(); i++) {
    int k = kmp[i - 1];
    while (now[k] != now[i] && k > 0) k = kmp[k - 1];
    if (now[i] == now[k]) k++;
    kmp[i] = k;
  }
  string ret = now.substr(0, kmp[now.size() - 1]);
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int q;
  cin >> q;
  while (q--) {
    string s;
    cin >> s;
    deque<char> d;
    vector<char> v1, v2;
    for (auto i : s) d.push_back(i);
    while (d.size() > 1) {
      v1.push_back(d.front());
      v2.push_back(d.back());
      d.pop_front();
      d.pop_back();
    }
    int now = -1, l = 0, r = v1.size() - 1;
    while (l <= r) {
      bool bol = true;
      int mid = (l + r) / 2;
      for (int i = 0; i <= mid; i++)
        if (v1[i] != v2[i]) bol = false;
      if (bol) {
        now = max(now, mid);
        l = mid + 1;
        continue;
      }
      r = mid - 1;
    }
    string add = "";
    for (int i = 0; i <= now; i++) add += v1[i];
    for (int i = v1.size() - 1; i > now; i--) d.push_front(v1[i]);
    for (int i = v2.size() - 1; i > now; i--) d.push_back(v2[i]);
    string ans = "", re = add;
    reverse(re.begin(), re.end());
    string ans1 = "", ans2 = "";
    string try1 = "", try2 = "";
    for (auto i : d) try1 += i, try2 += i;
    reverse(try2.begin(), try2.end());
    ans1 = lpp(try1);
    ans2 = lpp(try2);
    if (ans1.size() > ans2.size())
      ans = ans1;
    else
      ans = ans2;
    cout << add << ans << re << endl;
  }
  return 0;
}
