#include <bits/stdc++.h>
using namespace std;
long long next() {
  long long x;
  cin >> x;
  return x;
}
const long long inf = 1e18, mod = 998244353;
const int intf = 2e9, maxn = 1e5;
const double PI = 3.141592653589, eps = 1e-9;
struct Hash1 {
  struct MyHash {
    long long x, y;
    const long long M1 = 1e9 + 7, M2 = 1e9 + 9;
    MyHash() {}
    MyHash(long long x, long long y) : x(x), y(y) {}
    MyHash operator=(MyHash p) {
      x = p.x, y = p.y;
      return MyHash(x, y);
    }
    bool operator==(MyHash p) const { return x == p.x && y == p.y; }
    bool operator!=(MyHash p) const { return x != p.x || y != p.y; }
    MyHash operator+(MyHash p) const {
      return {(x + p.x) % M1, (y + p.y) % M2};
    }
    MyHash operator-(MyHash p) const {
      return {(x - p.x + M1) % M1, (y - p.y + M2) % M2};
    }
    MyHash operator*(MyHash p) const {
      return {(x * p.x) % M1, (y * p.y) % M2};
    }
  };
  int n;
  vector<MyHash> h, d;
  MyHash p = MyHash(101, 103);
  Hash1() {}
  Hash1(string s) : n(s.size()) {
    h.assign(n + 1, MyHash(0, 0));
    d.assign(n + 1, MyHash(1, 1));
    for (int i = 1; i <= n; i++) {
      d[i] = d[i - 1] * p;
      h[i] = h[i - 1] * p + MyHash(s[i - 1], s[i - 1]);
    }
  }
  MyHash get_hash(int l, int r) {
    l++, r++;
    return h[r] - h[l - 1] * d[r - l + 1];
  }
  MyHash get_hash(int l1, int r1, int l2, int r2) {
    MyHash ans = get_hash(l1, r1) * d[r2 - l2 + 1] + get_hash(l2, r2);
    return ans;
  }
  bool pruf(int l1, int r1, int l2, int r2) {
    return get_hash(l1, r1) == get_hash(l2, r2);
  }
};
struct Hash {
  struct MyHash {
    long long x, y;
    const long long M1 = 1e9 + 7, M2 = 1e9 + 9;
    MyHash() {}
    MyHash(long long x) : x(x) {}
    MyHash operator=(MyHash p) {
      x = p.x;
      return MyHash(x);
    }
    bool operator==(MyHash p) const { return x == p.x; }
    bool operator!=(MyHash p) const { return x != p.x; }
    MyHash operator+(MyHash p) const { return {(x + p.x) % M1}; }
    MyHash operator-(MyHash p) const { return {(x - p.x + M1) % M1}; }
    MyHash operator*(MyHash p) const { return {(x * p.x) % M1}; }
  };
  int n;
  vector<MyHash> h, d;
  MyHash p = MyHash(101);
  Hash() {}
  Hash(string s) : n(s.size()) {
    h.assign(n + 1, MyHash(0));
    d.assign(n + 1, MyHash(1));
    for (int i = 1; i <= n; i++) {
      d[i] = d[i - 1] * p;
      h[i] = h[i - 1] * p + MyHash(s[i - 1]);
    }
  }
  MyHash get_hash(int l, int r) {
    l++, r++;
    return h[r] - h[l - 1] * d[r - l + 1];
  }
  MyHash get_hash(int l1, int r1, int l2, int r2) {
    MyHash ans = get_hash(l1, r1) * d[r2 - l2 + 1] + get_hash(l2, r2);
    return ans;
  }
  bool pruf(int l1, int r1, int l2, int r2) {
    return get_hash(l1, r1) == get_hash(l2, r2);
  }
};
bool PRINT = false;
Hash h, rev;
string s;
int n;
string solve1() {
  vector<int> d1(n);
  int l = 0, r = -1;
  for (int i = 0; i < n; i++) {
    int k = i > r ? 1 : min(d1[l + r - i], r - i + 1);
    while (i + k < n && i - k >= 0 && s[i + k] == s[i - k]) ++k;
    d1[i] = k;
    if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;
  }
  vector<int> d2(n);
  l = 0, r = -1;
  for (int i = 0; i < n; i++) {
    int k = i > r ? 0 : min(d2[l + r - i + 1], r - i + 1);
    while (i + k < n && i - k - 1 >= 0 && s[i + k] == s[i - k - 1]) ++k;
    d2[i] = k;
    if (i + k - 1 > r) l = i - k, r = i + k - 1;
  }
  vector<vector<pair<int, int> > > lst(n);
  for (int i = 0; i < n; i++) {
    lst[i - d1[i] + 1].emplace_back(i, 0);
    lst[i - d2[i]].emplace_back(i - 1, 1);
  }
  l = 0;
  int type = -1;
  pair<int, int> ans;
  set<pair<int, int> > st;
  for (auto x : lst[0]) st.insert(x);
  for (int i = 0; i < n; i++) {
    if (h.get_hash(0, i) != rev.get_hash(0, i)) continue;
    int j = n - i - 1;
    if (j < i) continue;
    pair<int, int> cur = {i + 1, 0};
    for (auto x : lst[i + 1]) st.insert(x);
    auto it = st.upper_bound(make_pair((i + j) / 2, 1 - ((j - i + 1) % 2)));
    if (it != st.begin()) {
      it--;
      if (it->second == 0)
        cur.second = max(cur.second, 2 * (it->first - i) - 1);
      else
        cur.second = max(cur.second, 2 * (it->first - i));
    }
    if (cur.first * 2 + cur.second > l) {
      l = cur.first * 2 + cur.second;
      ans = cur;
      type = 1;
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    if (i + 1 > l && h.get_hash(0, i) == rev.get_hash(n - i - 1, n - 1)) {
      l = i + 1;
      ans = {i + 1, 0};
      type = 2;
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    if (i + 1 > l && rev.get_hash(0, i) == h.get_hash(n - i - 1, n - 1)) {
      l = i + 1;
      ans = {i + 1, 0};
      type = 3;
    }
  }
  string anss = "";
  if (type == 1) {
    anss = s.substr(0, ans.first + ans.second) +
           s.substr(n - ans.first, ans.first);
  } else if (type == 2) {
    anss = s.substr(0, ans.first);
  } else {
    anss = s.substr(n - ans.first, ans.first);
  }
  return anss;
}
void solve() {
  cin >> s;
  h = Hash(s);
  reverse((s).begin(), (s).end());
  rev = Hash(s);
  reverse((s).begin(), (s).end());
  n = s.size();
  if (h.get_hash(0, n - 1) == rev.get_hash(0, n - 1)) {
    cout << s << '\n';
    return;
  }
  string ans1 = solve1();
  reverse((s).begin(), (s).end());
  h = Hash(s);
  reverse((s).begin(), (s).end());
  rev = Hash(s);
  reverse((s).begin(), (s).end());
  string ans2 = solve1();
  reverse((ans2).begin(), (ans2).end());
  if (ans1.size() > ans2.size())
    cout << ans1 << '\n';
  else
    cout << ans2 << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout.precision(20);
  for (int t = next(); t--;) solve();
  return 0;
}
