#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int tc, n, f[N];
string t, s;
int solve(string s) {
  string res = s;
  int len;
  reverse(s.begin(), s.end());
  s = res + "#" + s;
  f[0] = 0;
  int i = 0, j = 1;
  len = s.size();
  while (j < len) {
    if (s[i] == s[j]) {
      f[j] = i + 1;
      i++;
      j++;
    } else {
      if (i >= 1) {
        i = f[i - 1];
      } else {
        f[j] = 0;
        j++;
      }
    }
  }
  int ans = f[len - 1];
  for (int i = 0; i < len; i++) {
    f[i] = 0;
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> tc;
  while (tc--) {
    cin >> s;
    int i = 0, j = s.size() - 1;
    for (; i < j; i++, j--) {
      if (s[i] != s[j]) {
        break;
      }
    }
    if (i >= j) {
      cout << s << "\n";
    } else {
      string t = s.substr(i, j - i + 1);
      string tt = t;
      reverse(tt.begin(), tt.end());
      int a = solve(t), b = solve(tt);
      cout << s.substr(0, i);
      if (a > b) {
        cout << t.substr(0, a);
      } else {
        cout << tt.substr(0, b);
      }
      cout << s.substr(j + 1, s.size() - j - 1) << "\n";
    }
  }
}
