#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
int in() {
  int x;
  cin >> x;
  return x;
}
long long lin() {
  long long x;
  cin >> x;
  return x;
}
string stin() {
  string s;
  cin >> s;
  return s;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
vector<int> iota(int n) {
  vector<int> a(n);
  iota(begin(a), end(a), 0);
  return a;
}
void print() { putchar(' '); }
void print(bool a) { cout << a; }
void print(int a) { cout << a; }
void print(long long a) { cout << a; }
void print(char a) { cout << a; }
void print(string& a) { cout << a; }
void print(double a) { cout << a; }
template <class T>
void print(const vector<T>&);
template <class T, size_t size>
void print(const array<T, size>&);
template <class T, class L>
void print(const pair<T, L>& p);
template <class T, size_t size>
void print(const T (&)[size]);
template <class T>
void print(const vector<T>& a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
  cout << endl;
}
template <class T>
void print(const deque<T>& a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, size_t size>
void print(const array<T, size>& a) {
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, class L>
void print(const pair<T, L>& p) {
  cout << '(';
  print(p.first);
  cout << ",";
  print(p.second);
  cout << ')';
}
template <class T, size_t size>
void print(const T (&a)[size]) {
  print(a[0]);
  for (auto i = a; ++i != end(a);) {
    cout << " ";
    print(*i);
  }
}
template <class T>
void print(const T& a) {
  cout << a;
}
int out() {
  putchar('\n');
  return 0;
}
template <class T>
int out(const T& t) {
  print(t);
  putchar('\n');
  return 0;
}
template <class Head, class... Tail>
int out(const Head& head, const Tail&... tail) {
  print(head);
  putchar(' ');
  out(tail...);
  return 0;
}
long long gcd(long long a, long long b) {
  while (b) {
    long long c = b;
    b = a % b;
    a = c;
  }
  return a;
}
long long lcm(long long a, long long b) {
  if (!a || !b) return 0;
  return a * b / gcd(a, b);
}
const int INF = 1061109567;
const long long LINF = 4557430888798830399LL;
int pi[2000002];
string prep(string s) {
  string a = s;
  reverse(a.begin(), a.end());
  a = s + "0" + a;
  int l = a.size();
  int j = 0;
  for (long long i = 1; i <= l - 1; ++i) {
    while (j > 0 && a[i] != a[j]) j = pi[j - 1];
    if (a[i] == a[j]) j++;
    pi[i] = j;
  }
  return a.substr(0, j);
}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ;
  int test = in();
  string s;
  int h, t;
  for (long long i = 0; i < test; i++) {
    s = stin();
    h = 0;
    t = s.size() - 1;
    while (s[h] == s[t] && h < t) {
      h++;
      t--;
    }
    if (h > 0) cout << s.substr(0, h);
    if (2 * h < s.size()) {
      string remain = s.substr(h, t - h + 1);
      string pre = prep(remain);
      reverse(remain.begin(), remain.end());
      string suf = prep(remain);
      cout << (pre.size() > suf.size() ? pre : suf);
    }
    if (h > 0) cout << s.substr(t + 1, h);
    cout << '\n';
  }
}
