#include <bits/stdc++.h>
using namespace std;
array<vector<int>, 2> manacher(const string& s) {
  int n = s.length();
  array<vector<int>, 2> p = {vector<int>(n + 1), vector<int>(n)};
  for (int z = 0; z < 2; z++)
    for (int i = 0, l = 0, r = 0; i < n; i++) {
      int t = r - i + !z;
      if (i < r) p[z][i] = min(t, p[z][l + t]);
      int L = i - p[z][i], R = i + p[z][i] - !z;
      while (L >= 1 && R + 1 < n && s[L - 1] == s[R + 1]) p[z][i]++, L--, R++;
      if (R > r) l = L, r = R;
    }
  return p;
}
int n;
string s;
int main() {
  int t;
  cin >> t;
  while (t--) {
    cin >> s;
    n = s.length();
    array<vector<int>, 2> man = manacher(s);
    int matches = 0;
    for (int i = 0; i < s.length() / 2; i++) {
      if (s[i] != s[s.length() - i - 1]) break;
      matches++;
    }
    int maxi = min(matches * 2 + 1, (int)s.length());
    int l = matches - 1, r = n - matches;
    if (l + 1 != r) l++;
    for (int i = 0; i < s.length(); i++) {
      int min0 = min(i - man[0][i], n - i - man[0][i]);
      int min1 = min(i - man[1][i], n - 1 - i - man[1][i]);
      if (min0 <= matches) {
        int curr = 2 * (min0 + man[0][i]);
        if (curr > maxi) {
          maxi = curr;
          l = min0 - 1, r = n - min0;
          if (i - man[0][i] == l + 1)
            l += 2 * man[0][i];
          else
            r -= 2 * man[0][i];
        }
      }
      if (min1 <= matches) {
        int curr = 2 * (min1 + man[1][i]) + 1;
        if (curr > maxi) {
          maxi = curr;
          l = min1 - 1, r = n - min1;
          if (i - man[1][i] == l + 1)
            l += (2 * man[1][i] + 1);
          else
            r -= (2 * man[1][i] + 1);
        }
      }
    }
    for (int i = 0; i <= l; i++) printf("%c", s[i]);
    for (int i = r; i <= n - 1; i++) printf("%c", s[i]);
    puts("");
  }
  return 0;
}
