// Code By H~$~C

module main;

import std.stdio, std.array, std.string, std.math, std.uni, std.format, std.bigint;
import std.algorithm, std.conv, std.container, std.range, std.functional;
import std.random, std.typecons;

// FIXME
int[] buildZ(in string s) {
  int n = cast(int)(s.length);
  int[] z; z.length = n;
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r) z[i] = (z[i - l] < r - i + 1 ? z[i - l] : r - i + 1);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}

void solve(in int testcase) {
  string s, t;
  s.read;
  int n = cast(int)(s.length), m;
  for (int i = 0; i < n; ++i)
    t ~= s[n - i - 1];
  if (s == t) {
    s.writeln;
    return ;
  }
  int[] z = buildZ(s ~ '$' ~ t);
  int x = z[n + 1];
  string ans1 = s[0 .. x];
  string ans2 = "";
  int mx = 0;
  string p = s[x .. n - x];
  string o;
  {
    n = cast(int)(p.length), m = n * 2 + 1;
    t = "";
    for (int i = 0; i < n; ++i)
      t ~= p[n - i - 1];
    o = p ~ '$' ~ t;
    z = buildZ(o);
    for (int i = m - 1; i >= 0; --i) {
      if (z[i] == m - i && mx < m - i) {
        mx = m - i;
        ans2 = o[i .. $];
      }
    }
  }
  p = t;
  {
    n = cast(int)(p.length), m = n * 2 + 1;
    t = "";
    for (int i = 0; i < n; ++i)
      t ~= p[n - i - 1];
    o = p ~ '$' ~ t;
    z = buildZ(o);
    for (int i = m - 1; i >= 0; --i) {
      if (z[i] == m - i && mx < m - i) {
        mx = m - i;
        ans2 = o[i .. $];
      }
    }
  }
  string ans3;
  for (int i = 0; i < x; ++i)
    ans3 ~= ans1[x - i - 1];
  (ans1 ~ ans2 ~ ans3).writeln;
}

// ************************************************************

T reader(T)() { return readToken().to!T; }
void read(T)(ref T t) { t = reader!T; }
T[] readarray(T)() { return readln.splitter.map!(to!T).array; }
void chmax(T)(ref T a, T b) { a = max(a, b); }
void chmin(T)(ref T a, T b) { a = min(a, b); }
alias less = (a, b) => a < b;
alias greater = (a, b) => a > b;
T min_element(T)(in T[] a) { return a.element!less; }
T max_element(T)(in T[] a) { return a.element!greater; }
alias unique = uniq;

// constant or some variables
immutable int inf = 0x3f3f3f3f;
immutable long lnf = 0x3f3f3f3f3f3f3f3f;
immutable typeof(null) NULL = null;
string[] _tokens;

// functions
T element(alias pred, T)(in T[] a) {
  int pos = 0;
  for (int i = 1; i < cast(int)(a.length); ++i)
    if (binaryFun!pred(a[i], a[pos])) pos = i;
  return a[pos];
}
string readToken() {
  for (; _tokens.empty; ) {
    if (stdin.eof) return "";
    _tokens = readln.split;
  }
  auto token = _tokens.front;
  _tokens.popFront;
  return token;
}
int binary_bearch(alias pred, T)(in T[] as) {
  int l = -1, h = cast(int)(as.length), mid;
  for (; l + 1 < h; ) {
    mid = (l + h) >> 1;
    (unaryFun!pred(as[mid]) ? h : l) = mid;
  }
  return h;
}
int lower_bound(alias pred = less, T)(in T[] as, T val) {
  return as.binary_bearch!(a => a == val || pred(val, a));
}
int upper_bound(alias pred = less, T)(in T[] as, T val) {
  return as.binary_bearch!(a => pred(val, a));
}

void main(string[] args) {
  int tests = 1;
  tests.read();
  foreach(test; 1 .. tests + 1) solve(test);
}
