#include <bits/stdc++.h>
using namespace std;
template <int ALPHA>
struct PalTree {
  struct node {
    int start, end;
    int next[ALPHA];
    int suffix;
    node() { fill(next, next + ALPHA, -1); }
  };
  string s;
  vector<node> nodes;
  int cur;
  PalTree() : nodes(2) {
    nodes[0].start = 0;
    nodes[0].end = -1;
    nodes[0].suffix = 0;
    nodes[1].start = 0;
    nodes[1].end = 0;
    nodes[1].suffix = 0;
    cur = 0;
  }
  int length(int i) { return nodes[i].end - nodes[i].start; }
  int& slink(int i) { return nodes[i].suffix; }
  int& next(int i, int c) { return nodes[i].next[c]; }
  void insert(int c) {
    s.push_back(c);
    int parent = cur;
    for (; s.size() < length(parent) + 2 ||
           s.back() != s[s.size() - length(parent) - 2];
         parent = slink(parent))
      ;
    if (next(parent, c) >= 0) {
      cur = next(parent, c);
      return;
    }
    next(parent, c) = nodes.size();
    cur = nodes.size();
    nodes.push_back({});
    nodes.back().end = s.size();
    nodes.back().start = s.size() - length(parent) - 2;
    parent = slink(parent);
    if (length(cur) == 1) {
      slink(cur) = 1;
      return;
    }
    for (; s.size() < length(parent) + 2 ||
           s.back() != s[s.size() - length(parent) - 2];
         parent = slink(parent))
      ;
    slink(cur) = next(parent, c);
  }
};
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int n = s.size();
    string x;
    x.reserve(n / 2);
    int a = 0, b = n - 1;
    while ((x.size() < n / 2) && s[a] == s[b] && a < n && b >= 0) {
      x.push_back(s[a]);
      a++;
      b--;
    }
    string t = x;
    int l = n - 2 * x.size();
    pair<int, int> best = {a, a};
    {
      PalTree<26> p;
      for (int i = a; i <= b; i++) {
        p.insert(s[i] - ('a' + 0));
      }
      for (int i = 2; i < p.nodes.size(); i++) {
        if (p.nodes[i].start != 0) continue;
        if (p.length(i) > (best.second - best.first)) {
          best = {p.nodes[i].start + a, p.nodes[i].end + a};
        }
      }
    }
    {
      PalTree<26> p;
      for (int i = b; i >= a; i--) {
        p.insert(s[i] - ('a' + 0));
      }
      for (int i = 2; i < p.nodes.size(); i++) {
        if (p.nodes[i].start != 0) continue;
        if (p.length(i) > (best.second - best.first)) {
          int u = p.nodes[i].start, v = p.nodes[i].end - 1;
          u = b - u, v = b - v;
          best = {v, u + 1};
        }
      }
    }
    t.insert(t.end(), s.begin() + best.first, s.begin() + best.second);
    t.insert(t.end(), x.rbegin(), x.rend());
    cout << t << "\n";
  }
  return 0;
}
