This is the hard version of the problem. The difference is the constraint on the sum of lengths of strings and the number of test cases. You can make hacks only if you solve all versions of this task.

You are given a string $s$, consisting of lowercase English letters. Find the longest string, $t$, which satisfies the following conditions:   The length of $t$ does not exceed the length of $s$.  $t$ is a palindrome.  There exists two strings $a$ and $b$ (possibly empty), such that $t = a + b$ ( "$+$" represents concatenation), and $a$ is prefix of $s$ while $b$ is suffix of $s$. 


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^5$), the number of test cases. The next $t$ lines each describe a test case.

Each test case is a non-empty string $s$, consisting of lowercase English letters.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed $10^6$.


-----Output-----

For each test case, print the longest string which satisfies the conditions described above. If there exists multiple possible solutions, print any of them.


-----Example-----
Input
5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba

Output
a
abcdfdcba
xyzyx
c
abba



-----Note-----

In the first test, the string $s = $"a" satisfies all conditions.

In the second test, the string "abcdfdcba" satisfies all conditions, because:  Its length is $9$, which does not exceed the length of the string $s$, which equals $11$.  It is a palindrome.  "abcdfdcba" $=$ "abcdfdc" $+$ "ba", and "abcdfdc" is a prefix of $s$ while "ba" is a suffix of $s$. 

It can be proven that there does not exist a longer string which satisfies the conditions.

In the fourth test, the string "c" is correct, because "c" $=$ "c" $+$ "" and $a$ or $b$ can be empty. The other possible solution for this test is "s".

Difficulty: MEDIUM

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def manacher(S):
	N = len(S)
	(r, p) = (0, 0)
	A = [0] * N
	for i in range(N):
		if i <= r:
			A[i] = min(A[2 * p - i], r - i)
		else:
			A[i] = 0
		while i - A[i] - 1 >= 0 and i + A[i] + 1 < N and (S[i - A[i] - 1] == S[i + A[i] + 1]):
			A[i] += 1
		if r < i + A[i]:
			r = i + A[i]
			p = i
	return A

def f(S):
	return ''.join([i for i in S if i != '#'])
for i in range(int(input())):
	b = input().strip()
	n = len(b)
	if n % 2 == 0:
		c = ''
		v = b[:n // 2]
	else:
		c = b[n // 2]
		v = b[:n // 2]
	for i in range(n // 2):
		if b[i] != b[n - 1 - i]:
			c = b[i:n - i]
			v = b[:i]
			break
	a = '#'.join(c)
	a = '#' + a + '#'
	A = manacher(a)
	ans1 = ''
	for i in range(len(c), 0, -1):
		if i == A[i]:
			ans1 = a[:i * 2]
			break
	ans1 = f(ans1)
	ans2 = ''
	for i in range(len(c), 0, -1):
		if i == A[-1 - i]:
			ans2 = a[-i * 2 - 1:]
			break
	ans2 = f(ans2)
	if len(ans1) > len(ans2):
		ans = ans1
	else:
		ans = ans2
	print(v + ans + v[::-1])


from sys import stdin
from collections import defaultdict, Counter
from math import gcd

def solver(s):
	n = len(s)
	i = 0
	for i in range(n // 2):
		if s[i] != s[-(i + 1)]:
			break
	if i == 0:
		sub = s
	else:
		sub = s[i:-i]
	l = long_palindrome_ps(sub)
	return s[:i] + l + s[::-1][:i][::-1]

def long_palindrome_ps(s):
	n = len(s)
	lps = []
	ss = s + '#' + s[::-1]
	lps = lps_(ss)
	m_p = lps[-1]
	m_pp = s[:m_p]
	ss = s[::-1] + '#' + s
	lps = lps_(ss)
	m_s = lps[-1]
	m_sp = s[::-1][:m_s]
	if m_p > m_s:
		return m_pp
	else:
		return m_sp

def lps_(s):
	n = len(s)
	tr = [0]
	j = 0
	for i in range(1, n):
		if s[i] == s[j]:
			j += 1
			tr.append(j)
		else:
			while s[j] != s[i] and j > 0:
				j = tr[j - 1]
			if s[j] == s[i]:
				j += 1
				tr.append(j)
			elif j == 0:
				tr.append(j)
	return tr
T = int(input())
for _ in range(T):
	s = stdin.readline().strip()
	print(solver(s))


import os
import sys
from io import BytesIO, IOBase

def pie(s):
	s = s + '#' + s[::-1]
	n = len(s)
	pi = [0] * n
	j = 0
	for i in range(1, n):
		while j != 0 and s[i] != s[j]:
			j = pi[j - 1]
		j += s[i] == s[j]
		pi[i] = j
	return j

def main():
	for _ in range(int(input())):
		s = input().rstrip()
		n = len(s)
		(i, j) = (0, n - 1)
		while i <= j and s[i] == s[j]:
			i += 1
			j -= 1
		if i > j:
			print(s)
		else:
			ss = s[i:j + 1]
			ma1 = pie(ss)
			ma2 = pie(ss[::-1])
			if ma1 > ma2:
				print(s[:i] + ss[:ma1] + s[j + 1:])
			else:
				print(s[:i] + ss[-ma2:] + s[j + 1:])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def pre(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi
for _ in range(int(input())):
	i = 0
	s = input()
	j = len(s) - 1
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			break
	ans = ['', '', '']
	ans[0] = s[:i]
	ans[2] = ans[0][::-1]
	s = s[i:j + 1]
	if not len(s):
		print(''.join(ans))
		continue
	st = s + '#' + s[::-1]
	mx = pre(st)[-1]
	ans[1] = s[:mx]
	s = s[::-1]
	st = s + '#' + s[::-1]
	mx = pre(st)[-1]
	if mx > len(ans[1]):
		ans[1] = s[:mx]
	print(''.join(ans))


import sys
input = sys.stdin.readline
t = int(input())
ret = ''
for _ in range(t):
	suf = []
	s = list(input().rstrip())
	l = 0
	r = len(s) - 1
	while r - l > 1 and s[l] == s[r]:
		suf.append(s[l])
		l += 1
		r -= 1
	s = '$'.join(s[l:r + 1])
	i = 0
	j = 0
	length = len(s)
	par = [0] * length
	while i < length:
		while i - j >= 0 and i + j < length and (s[i - j] == s[i + j]):
			j += 1
		par[i] = j
		k = 1
		while i - k >= 0 and i + k < length and (k + par[i - k] < j):
			par[i + k] = par[i - k]
			k += 1
		i += k
		j -= k
	radius = 1
	mid = 0
	is_front = True
	for (i, item) in enumerate(par):
		if item == i + 1 and item > radius:
			radius = item
			mid = i
			is_front = True
		if item == length - i and item > radius:
			radius = item
			mid = i
			is_front = False
	if is_front:
		left = s[:mid + radius]
	else:
		left = s[mid - radius:]
	core = []
	for ch in left:
		if ch == '$':
			continue
		core.append(ch)
	core_s = ''.join(core)
	suf_s = ''.join(suf)
	pre_s = ''.join(suf[::-1])
	ans = ''.join([suf_s, core_s, pre_s])
	print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_str():
	return input().decode().strip()

def rint():
	return map(int, input().split())

def oint():
	return int(input())

def find_maxp(s):
	t = '#'.join('^{}$'.format(s))
	n = len(t)
	p = [0] * n
	c = 0
	r = 0
	for i in range(1, n - 1):
		p[i] = r > i and min(r - i, p[2 * c - i])
		while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
			p[i] += 1
		if i + p[i] > r:
			(c, r) = (i, i + p[i])
	(maxl, ci) = max(((n, i) for (i, n) in enumerate(p) if (i - n) // 2 == 0 or (i + n) // 2 == len(s)))
	return s[(ci - maxl) // 2:(ci + maxl) // 2]
t = oint()
for _ in range(t):
	s = get_str()
	li = 0
	ri = len(s) - 1
	if ri == 0:
		print(s[0])
		continue
	ps_len = 0
	while li < ri:
		if s[li] == s[ri]:
			ps_len += 1
			li += 1
			ri -= 1
		else:
			break
	left_len = 0
	right_len = 0
	midp = find_maxp(s[li:ri + 1])
	print(s[:li] + midp + s[ri + 1:])


import os
import sys
from io import BytesIO, IOBase
_print = print
BUFSIZE = 8192

def dbg(*args, **kwargs):
	_print('\x1b[95m', end='')
	_print(*args, **kwargs)
	_print('\x1b[0m', end='')

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def inp():
	return sys.stdin.readline().rstrip()

def mpint():
	return map(int, inp().split(' '))

def itg():
	return int(inp())

def partial(s) -> list:
	(g, pi) = (0, [0] * len(s))
	for i in range(1, len(s)):
		while g and s[g] != s[i]:
			g = pi[g - 1]
		pi[i] = g = g + (s[g] == s[i])
	return pi

def longest_palindromic_prefix(s):
	s += '#' + s[::-1]
	return s[:partial(s)[-1]]

def solve():
	s = inp()
	n = len(s)
	p_len = 0
	for i in range(n >> 1):
		if s[i] == s[-i - 1]:
			p_len = i + 1
		else:
			break
	s_pre = s[:p_len]
	s_suf = s[:p_len][::-1]
	if p_len:
		s = s[p_len:-p_len]
	s_mid = longest_palindromic_prefix(s)
	longest_suffix = longest_palindromic_prefix(s[::-1])
	if len(longest_suffix) > len(s_mid):
		s_mid = longest_suffix
	return s_pre + s_mid + s_suf

def main():
	for _ in range(itg()):
		print(solve())
DEBUG = 0
URL = 'https://codeforces.com/contest/1326/problem/D2'
if DEBUG == 1:
	import requests
	from ACgenerator.Y_Test_Case_Runner import TestCaseRunner
	runner = TestCaseRunner(main, URL)
	inp = runner.input_stream
	print = runner.output_stream
	runner.checking()
else:
	if DEBUG != 2:
		dbg = lambda *args, **kwargs: ...
		(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	if DEBUG == 3:

		def print(*args, **kwargs):
			_print(*args, **kwargs)
			sys.stdout.flush()
	main()


def isPali(s, i, j):
	half = (j - i + 1) // 2
	for k in range(half):
		if s[i + k] != s[j - k]:
			return False
	return True
for t in range(int(input())):
	s = input()
	ls = len(s)
	(i, j) = (0, ls - 1)
	if isPali(s, i, j):
		print(s)
		continue
	while s[i] == s[j]:
		i += 1
		j -= 1
	pre = s[:i]
	post = s[j + 1:]
	r = s[i:j + 1]
	lr = len(r)

	def longest_palindrome_prefix(r):
		if not r:
			return 0
		r = r + '#' + r[::-1] + '$'
		i = 0
		j = -1
		nt = [0] * len(r)
		nt[0] = -1
		while i < len(r) - 1:
			if j == -1 or r[i] == r[j]:
				i += 1
				j += 1
				nt[i] = j
			else:
				j = nt[j]
		return nt[len(r) - 1]
	lc1 = longest_palindrome_prefix(r)
	lc2 = longest_palindrome_prefix(r[::-1])
	maxLc = max(lc1, lc2)
	if isPali(r, 0, maxLc - 1):
		conj = r[0:maxLc]
	else:
		conj = r[lr - maxLc:lr]
	ans = pre + conj + post
	print(ans)


import math
import sys
from collections import defaultdict, Counter, deque, OrderedDict
import bisect
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]
from itertools import accumulate, groupby
import sys
mod = 1000000007

def prefix(s, lsa):
	index = 0
	i = 1
	while i < n:
		if s[i] == s[index]:
			lsa[i] = index + 1
			i += 1
			index += 1
		elif index == 0:
			lsa[i] = 0
			i += 1
		else:
			index = lsa[index - 1]
	return lsa[-1]
for _ in range(int(input())):
	s = input()
	ans = ''
	n = len(s)
	for i in range(n // 2):
		if s[i] == s[n - i - 1]:
			ans += s[i]
		else:
			break
	s = s[len(ans):len(s) - len(ans)]
	ss = ans
	tmp = s + '#' + s[::-1]
	n = len(tmp)
	lsa = [0] * n
	pre = prefix(tmp, lsa)
	tmp = s[::-1] + '#' + s
	suf = prefix(tmp, lsa)
	if pre >= suf:
		ans += s[:pre]
	else:
		s = s[::-1]
		ans += s[:suf]
	print(ans + ss[::-1])


T = int(input())

def manachers(T):
	C = 0
	R = -1
	rad = 0
	P = [0] * len(T)
	for i in range(len(T)):
		if i <= R:
			rad = min(P[2 * C - i], R - i)
		else:
			rad = 0
		while i + rad < len(T) and i - rad >= 0 and (T[i - rad] == T[i + rad]):
			rad += 1
		P[i] = rad
		if i + rad - 1 > R:
			C = i
			R = i + rad - 1
	return P

def pal(s, start, end):
	T = '*'.join(s[start:end + 1])
	P = manachers(T)
	center = 0
	size = 0
	for (i, el) in enumerate(P):
		if el == i + 1:
			center = i
			size = el
	answer = [c for c in T[center - size + 1:center + size] if c != '*']
	return answer
for t in range(T):
	s = input()
	N = len(s)
	start = []
	i = 0
	while s[i] == s[N - 1 - i] and i < N - 1 - i:
		start.append(s[i])
		i += 1
	palin1 = pal(s, i, N - 1 - i)
	palin2 = pal(s[::-1], i, N - 1 - i)
	if len(palin1) >= len(palin2):
		palin = palin1
	else:
		palin = palin2
	answer = start + list(palin) + start[::-1]
	assert len(answer) <= N
	print(''.join(answer))


def main():
	import sys
	input = sys.stdin.readline

	def manacher(S):
		C = []
		for a in S:
			C.append(a)
			C.append(0)
		C.pop()
		L = len(C)
		R = [0] * L
		i = j = 0
		while i < L:
			while j <= i < L - j and C[i - j] == C[i + j]:
				j += 1
			R[i] = j
			k = 1
			while j - R[i - k] > k <= i < L - k:
				R[i + k] = R[i - k]
				k += 1
			i += k
			j -= k
		return R
	for _ in range(int(input())):
		S = input().rstrip('\n')
		N = len(S)
		if N == 1:
			print(S)
			continue
		ii = -1
		for i in range(N // 2):
			if S[i] != S[N - 1 - i]:
				break
			ii = i
		if ii >= 0:
			ss = S[:ii + 1]
			S = S[ii + 1:N - ii - 1]
		else:
			ss = ''
		N = len(S)
		if N == 0:
			print(''.join([ss, ss[::-1]]))
			continue
		R = manacher(S)
		M = 0
		iii = 0
		for i in range(N):
			if R[i * 2] > M:
				if R[i * 2] % 2 == 0:
					continue
				k = R[i * 2] // 2
				if i - k == 0 or i + k == N - 1:
					M = R[i * 2]
					iii = i
		for i in range(N - 1):
			if R[i * 2 + 1] > M:
				if R[i * 2 + 1] % 2 == 1:
					continue
				k = R[i * 2 + 1] // 2
				if i - k + 1 == 0 or i + k == N - 1:
					M = R[i * 2 + 1]
					iii = i
		if M & 1:
			ans = S[iii - M // 2:iii + M // 2 + 1]
		else:
			ans = S[iii - M // 2 + 1:iii + M // 2 + 1]
		print(''.join([ss, ans, ss[::-1]]))
main()


import math
from bisect import bisect_left, bisect_right
from sys import stdin, stdout, setrecursionlimit
from collections import Counter
input = lambda : stdin.readline().strip()
print = stdout.write

def LPS(s):
	n = len(s)
	lps = [0] * n
	l = 0
	i = 1
	while i < n:
		if s[i] == s[l]:
			l += 1
			lps[i] = l
			i += 1
		elif l != 0:
			l = lps[l - 1]
		else:
			lps[i] = 0
			i += 1
	res = lps[n - 1]
	if res > n / 2:
		return n // 2
	else:
		return res
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	i = 0
	while i < n - i - 1:
		if s[i] == s[n - i - 1]:
			i += 1
		else:
			break
	if i > n - i - 1:
		print(s + '\n')
	else:
		string = s[i:n - i]
		right_index = i + LPS(string + '$' + string[::-1]) - 1
		left_index = n - i - LPS(string[::-1] + '$' + string)
		if right_index > n - left_index - 1:
			print(s[:i] + s[i:right_index + 1] + s[n - i:] + '\n')
		else:
			print(s[:i] + s[left_index:n - i] + s[n - i:] + '\n')


def RollingHash(S):
	h = 10 ** 11 + 7
	b = 10 ** 7 + 7
	L = len(S)
	ret = -1
	hashS = 0
	hashT = 0
	c = 1
	for i in range(L):
		hashS = (hashS * b + ord(S[i])) % h
		hashT = (hashT + ord(S[i]) * c) % h
		c = c * b % h
		if hashS == hashT:
			ret = i
	return S[:ret + 1]

def solve(S):
	T1 = RollingHash(S)
	T2 = RollingHash(S[::-1])
	if len(T1) < len(T2):
		return T2[::-1]
	return T1
import sys
input = sys.stdin.readline
Q = int(input())
Query = [list(input().rstrip()) for _ in range(Q)]
for S in Query:
	N = len(S)
	ind = 0
	while True:
		if S[ind] != S[N - 1 - ind] or ind >= N - 1 - ind:
			break
		ind += 1
	R = solve(S[ind:N - ind])
	ans = S[:ind] + R + S[N - ind:]
	print(''.join(ans))


import sys
import heapq
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt
from collections import defaultdict as dd, deque, Counter as c
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def post_process(string, ml, c):
	result = []
	for i in string[c - ml:c + ml + 1]:
		if i == '#':
			continue
		result.append(i)
	return ''.join(result)

def manacher(string):
	arr = ['#']
	for i in string:
		arr.append(i)
		arr.append('#')
	left = l1d(len(arr))
	(r, c) = (0, 0)
	for i in range(len(arr)):
		mirror = 2 * c - i
		if r > i:
			left[i] = min(r - i, left[mirror])
		try:
			while arr[i + 1 + left[i]] == arr[i - 1 - left[i]]:
				left[i] += 1
		except:
			pass
		if i + left[i] > r:
			c = i
			r = i + left[i]
	maxlength = 0
	center = 0
	for i in range(len(left)):
		if left[i] > maxlength and (i == left[i] or i + left[i] >= len(left) - 1):
			maxlength = left[i]
			center = i
	return post_process(arr, maxlength, center)
for _ in range(int(data())):
	s = data()
	if s[::-1] == s:
		out(s + '\n')
		continue
	(i, j) = (0, len(s) - 1)
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			break
	if i == 0:
		out(manacher(s) + '\n')
	else:
		out(s[:i] + manacher(s[i:j + 1]) + s[j + 1:] + '\n')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def pal(s):
	s = s + '#' + s[::-1]
	n = len(s)
	lps = [0] * n
	l = 0
	i = 1
	while i < n:
		if s[i] == s[l]:
			l = l + 1
			lps[i] = l
			i = i + 1
		elif l != 0:
			l = lps[l - 1]
		else:
			lps[i] = 0
			i = i + 1
	res = lps[n - 1]
	if res > n / 2:
		return s[:n // 2]
	else:
		return s[:res]
t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	d = 0
	for j in range(n // 2 - 1):
		if s[j] == s[n - j - 1]:
			d += 1
		else:
			break
	p = pal(s[d:n - d])
	p1 = pal(s[d:n - d][::-1])
	if len(p) > len(p1):
		s = s[:d] + p + s[n - d:]
	else:
		s = s[:d] + p1 + s[n - d:]
	print(s)


import sys
input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
	s = input().rstrip()
	(l, r) = (0, len(s) - 1)
	while l < r and s[l] == s[r]:
		l += 1
		r -= 1
	a = s[:l]
	b = s[r + 1:]
	s = s[l:r + 1]
	n = 2 * len(s) + 1
	if s == '':
		print(a + b)
		continue
	L = [0] * n
	L[1] = 1
	center = 1
	center_right = 2
	max_len = 1
	max_pos = 1
	for i in range(2, n):
		i_mirror = 2 * center - i
		diff = center_right - i
		if diff > 0:
			L[i] = min(L[i_mirror], diff)
		try:
			while i + L[i] < n and i - L[i] > 0 and ((i + L[i] + 1) % 2 == 0 or s[(i + L[i] + 1) // 2] == s[(i - L[i] - 1) // 2]):
				L[i] += 1
		except:
			pass
		if L[i] > max_len and (i - L[i] == 0 or i + L[i] == n - 1):
			max_len = L[i]
			max_pos = i
		if i + L[i] > center_right:
			center = i
			center_right = i + L[i]
	t = ''
	i = max_pos // 2
	if max_pos % 2 == 0:
		t = s[i - max_len // 2:i + max_len // 2]
	else:
		t = s[i - max_len // 2:i + max_len // 2 + 1]
	print(a + t + b)


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import Decimal
from decimal import *
from collections import defaultdict, deque
import heapq
from decimal import Decimal
getcontext().prec = 25
abcd = 'abcdefghijklmnopqrstuvwxyz'
MOD = pow(10, 9) + 7
BUFSIZE = 8192
from bisect import bisect_left, bisect_right

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def LongestPalindromicPrefix(Str):
	temp = Str + '?'
	Str = Str[::-1]
	temp = temp + Str
	n = len(temp)
	lps = [0] * n
	for i in range(1, n):
		Len = lps[i - 1]
		while Len > 0 and temp[Len] != temp[i]:
			Len = lps[Len - 1]
		if temp[i] == temp[Len]:
			Len += 1
		lps[i] = Len
	return temp[0:lps[n - 1]]
for _ in range(int(input())):
	s = input()
	n = len(s)
	i = 0
	s1 = s[::-1]
	while i < n:
		if s[i] != s1[i]:
			break
		i += 1
	if i == n:
		print(s)
		continue
	c = s[:i]
	pre = LongestPalindromicPrefix(s[i:n - i])
	suf = LongestPalindromicPrefix(s[i:n - i][::-1])
	if len(pre) < len(suf):
		pre = suf
	print(c + pre + c[::-1])


def ispalindrome(s):
	a = s + '.' + s[::-1]
	n = len(a)
	(j, p) = (0, [0] * n)
	for i in range(1, n):
		while j and a[j] != a[i]:
			j = p[j - 1]
		if a[j] == a[i]:
			j += 1
		p[i] = j
	return s[:j]
for _ in range(int(input())):
	s = input()
	if len(s) == 1:
		print(s)
		continue
	l = 0
	while l < len(s) - l - 1:
		if s[l] != s[len(s) - l - 1]:
			break
		l += 1
	m1 = ispalindrome(s[l:len(s) - l])
	m2 = ispalindrome(s[l:len(s) - l][::-1])
	if len(m1) < len(m2):
		m1 = m2
	print(s[:l] + m1 + s[len(s) - l:])


from sys import stdin, stdout

def solve(s):
	s = s + '#' + s[::-1]
	pre = [0] * len(s)
	c = 0
	for i in range(1, len(s)):
		while c != 0 and s[c] != s[i]:
			c = pre[c - 1]
		if s[c] == s[i]:
			c += 1
		pre[i] = c
	return s[0:c]

def main():
	t = int(stdin.readline())
	for _ in range(t):
		s = stdin.readline().rstrip()
		ans = ''
		c = 0
		for i in range(int(len(s) / 2)):
			if s[i] == s[len(s) - 1 - i]:
				c += 1
			else:
				break
		if c < int(len(s) / 2):
			if c == 0:
				ss = s
			else:
				ss = s[c:-c]
			ss2 = ss[::-1]
			ss = solve(ss)
			ss2 = solve(ss2)
			if len(ss2) >= len(ss):
				if c == 0:
					ans = ss2
				else:
					ans = s[:c] + ss2 + s[-c:]
			elif c == 0:
				ans = ss
			else:
				ans = s[:c] + ss + s[-c:]
		elif len(s) % 2 == 1:
			ans = s
		else:
			ans = s[:c] + s[-c:]
		stdout.write(ans + '\n')
main()


def lpp(s):
	a = s + '.' + s[::-1]
	n = len(a)
	(j, p) = (0, [0] * n)
	for i in range(1, n):
		while j and a[j] != a[i]:
			j = p[j - 1]
		if a[j] == a[i]:
			j += 1
		p[i] = j
	return s[:j]

def longest(s):
	(a, b) = (lpp(s), lpp(s[::-1]))
	return a if len(a) > len(b) else b

def problem(s):
	(i, j) = (0, len(s) - 1)
	while i < j and s[i] == s[j]:
		(i, j) = (i + 1, j - 1)
	if i >= j:
		return s
	return s[:i] + longest(s[i:j + 1]) + s[j + 1:]
for _ in range(int(input())):
	print(problem(input()))


import sys
inp = sys.stdin.readline

def input():
	return inp().strip()

def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))

def palindromCentre(s):
	S = []
	n = len(s)
	N = 2 * n + 1
	for i in s:
		S.append('#')
		S.append(i)
	S.append('#')
	p = [0] * N
	c = 0
	(L, R) = (0, 0)
	i = 0
	while i < N:
		if i > R:
			start = 1
			p[i] = 0
			(l1, r1) = (i - start, i + start)
			while l1 >= 0 and r1 < N and (S[l1] == S[r1]):
				p[i] += 1
				l1 -= 1
				r1 += 1
			c = i
			(L, R) = (c - p[i], c + p[i])
		else:
			r = i
			l = 2 * c - r
			if p[l] < R - r or (p[l] == R - r and R == N - 1):
				p[r] = p[l]
			else:
				start = R - r
				p[r] = start
				(l1, r1) = (i - start - 1, i + start + 1)
				while l1 >= 0 and r1 < N and (S[l1] == S[r1]):
					p[r] += 1
					l1 -= 1
					r1 += 1
				c = r
				(L, R) = (c - p[r], c + p[r])
		i += 1
	return (p, S)

def main():

	def red(ans):
		return ''.join([i for i in ans if i != '#'])
	T = iin()
	while T:
		T -= 1
		s = list(input())
		(s1, s2) = palindromCentre(s)
		n = len(s1)
		s3 = [0] * n
		for i in range(n // 2):
			if s2[i] == s2[-i - 1]:
				s3[i] += 1
				s3[-i - 1] += 1
			else:
				break
		ans = []
		for i in range(n // 2, n):
			(x, y) = (n - i - 1, i)
			if s3[x - s1[x]]:
				ch = x - s1[x]
				ans = s2[:ch] + s2[x - s1[x]:x + s1[x] + 1] + s2[-ch:] if ch else s2[x - s1[x]:x + s1[x] + 1]
				break
			if s3[n - (y + s1[y]) - 1]:
				ch = n - (y + s1[y]) - 1
				ans = s2[:ch] + s2[y - s1[y]:y + s1[y] + 1] + s2[-ch:] if ch else s2[y - s1[y]:y + s1[y] + 1]
				break
		print(red(ans))
main()


def longestPrefix(txt: str) -> str:
	txt = txt + '#' + txt[::-1]
	n = len(txt)
	(j, i) = (-1, 0)
	nextJ = [0] * n
	nextJ[0] = -1
	while i < n - 1:
		if j == -1 or txt[i] == txt[j]:
			i += 1
			j += 1
			if txt[i] == txt[j]:
				nextJ[i] = nextJ[j]
			else:
				nextJ[i] = j
		else:
			j = nextJ[j]
	(j, i) = (0, 1)
	dp = [0] * n
	while i < n:
		if j < 0 or txt[i] == txt[j]:
			dp[i] = j + 1
			i += 1
			j += 1
		elif j == 0:
			dp[i] = 0
			i += 1
		else:
			j = nextJ[j]
	return txt[:dp[-1]]

def longestPalindrome(line: str) -> str:
	(b, e) = (0, len(line) - 1)
	while b < e and line[b] == line[e]:
		b += 1
		e -= 1
	if b >= e:
		return line
	p1 = longestPrefix(line[b:e + 1])
	p2 = longestPrefix(line[b:e + 1][::-1])
	p = p1 if len(p1) >= len(p2) else p2
	return line[:b] + p + line[e + 1:]
n = int(input())
for i in range(n):
	line = input().strip(' \r\n')
	print(longestPalindrome(line))


def solve_palindrome(a: str) -> str:
	a += '#' + a[::-1]
	al = [0] * len(a)
	j = 0
	for i in range(1, len(a)):
		while j > 0 and a[i] != a[j]:
			j = al[j - 1]
		if a[i] == a[j]:
			j += 1
		al[i] = j
	return a[0:j]

def solve():
	a = input()
	b = a[::-1]
	j = 0
	while a[j] == b[j] and j * 2 < len(a) - 1:
		j += 1
	c = a[:j]
	b = b[j:len(b) - j]
	a = a[j:len(a) - j]
	aa = solve_palindrome(a)
	bb = solve_palindrome(b)
	if len(aa) < len(bb):
		aa = bb
	print(c + aa + c[::-1])
n = int(input())
for i in range(n):
	solve()


def kmp(s):
	l = len(s)
	ans = [-1 for i in range(l)]
	j = 0
	i = 1
	while i < l:
		if s[i] == s[j]:
			ans[i] = j
			j += 1
			i += 1
		elif j > 0:
			j = ans[j - 1] + 1
		else:
			i += 1
	return ans[l - 1] + 1

def find_pattern(s):
	temp = s + '?' + s[::-1]
	ans = kmp(temp)
	return ans
for _ in range(int(input())):
	a = input()
	n = len(a)
	i = 0
	j = n - 1
	l = 0
	ans = ''
	while i < j:
		if a[i] is a[j]:
			i += 1
			j -= 1
			l += 1
		else:
			break
	ans += a[:l]
	rem = a[i:j + 1]
	if i <= j:
		pre = find_pattern(rem)
		suf = find_pattern(rem[::-1])
		if pre > suf:
			ans += rem[:pre]
		else:
			ans += rem[::-1][:suf]
	ans += a[n - l:]
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	S = input().strip()
	ANSP = []
	f = 0
	l = len(S) - 1
	while f < l and S[f] == S[l]:
		ANSP.append(S[f])
		f += 1
		l -= 1
	if f == l or f == l + 1:
		print(S)
		continue
	S2 = S[f:l + 1]
	SS2 = []
	for s in S2:
		SS2.append(s)
		SS2.append('$')
	SS2.pop()
	LEN = len(SS2)
	i = 0
	j = 0
	R = [0] * LEN
	while i < LEN:
		while i - j >= 0 and i + j < LEN and (SS2[i - j] == SS2[i + j]):
			j += 1
		R[i] = j
		k = 1
		while i - k >= 0 and i + k < LEN and (k + R[i - k] < j):
			R[i + k] = R[i - k]
			k += 1
		i += k
		j -= k
	MAX = 0
	for i in range(LEN):
		if i - R[i] + 1 == 0 or i + R[i] == LEN:
			if MAX < R[i]:
				MAX = R[i]
				MAXind = i
	S3 = SS2[MAXind - MAX + 1:MAXind + MAX]
	SS3 = []
	for s in S3:
		if s != '$':
			SS3.append(s)
	sys.stdout.write(''.join(ANSP) + ''.join(SS3) + ''.join(ANSP[::-1]) + '\n')


def read_int():
	return int(input())

def read_int_n():
	return list(map(int, input().split()))

def read_float():
	return float(input())

def read_float_n():
	return list(map(float, input().split()))

def read_str():
	return input().strip()

def read_str_n():
	return list(map(str, input().split()))

def manacher(S):
	s = [0]
	for c in S:
		s.append(c)
		s.append(0)
	N = len(s)
	R = [0] * N
	i = 0
	j = 0
	while i < N:
		while i - j >= 0 and i + j < N and (s[i - j] == s[i + j]):
			j += 1
		R[i] = j
		k = 1
		while i - k >= 0 and i + k < N and (k + R[i - k] < j):
			R[i + k] = R[i - k]
			k += 1
		i += k
		j -= k
	return R

def slv(S):
	if S == S[::-1]:
		return S
	N = len(S)
	i = 0
	while i < N // 2:
		if S[i] != S[N - i - 1]:
			break
		i += 1
	s = S[i:N - i]
	ls = S[:i]
	rs = S[N - i:]
	mp = (0, -1, -1)
	for (j, rad) in enumerate(manacher(s)):
		l = max(0, -(-(j - rad) // 2))
		r = min((j + rad) // 2, len(s))
		if l == 0 or r == len(s):
			mp = max(mp, (r - l, l, r))
	return ls + s[mp[1]:mp[2]] + rs

def main():
	T = read_int()
	for _ in range(T):
		S = read_str()
		print(slv(S))
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getZarr(string, z):
	n = len(string)
	(l, r, k) = (0, 0, 0)
	for i in range(1, n):
		if i > r:
			(l, r) = (i, i)
			while r < n and string[r - l] == string[r]:
				r += 1
			z[i] = r - l
			r -= 1
		else:
			k = i - l
			if i + z[k] <= r:
				z[i] = z[k]
			else:
				l = i
				while r < n and string[r - l] == string[r]:
					r += 1
				z[i] = r - l
				r -= 1
		if z[i] == n - i:
			return z[i]
t = int(input())
for i in range(t):
	s = input()
	l = len(s)
	ind = -1
	for j in range(l // 2):
		if s[j] == s[l - j - 1]:
			continue
		else:
			ind = j
			break
	if ind == -1:
		print(s)
		continue
	if ind == 0:
		text = s[::-1]
		pattern = s
	else:
		text = s[l - ind - 1:ind - 1:-1]
		pattern = text[::-1]
	concat = pattern + '$' + text
	l1 = len(concat)
	z = [0] * l1
	ans1 = getZarr(concat, z)
	concat = text + '$' + pattern
	z = [0] * l1
	ans2 = getZarr(concat, z)
	pre = s[:ind]
	if ans1 >= ans2:
		print(pre + s[ind:ind + ans1] + pre[::-1])
	else:
		ind = l - ind - 1
		print(pre + s[ind:ind - ans2:-1] + pre[::-1])


import io
import os
import sys
cachedPow = {}
PRIME = 31
MOD = 2 ** 61 - 1
MOD = 10 ** 9 + 7

class RabinKarpRollingHash:

	def __init__(self, s, PRIME=PRIME, MOD=MOD):
		n = len(s)
		prefix = [0] * (n + 1)
		for i in range(n):
			prefix[i + 1] = (prefix[i] * PRIME + ord(s[i]) - ord('a')) % MOD
		if n not in cachedPow:
			cachedPow[0] = 1
			for i in range(n):
				cachedPow[i + 1] = cachedPow[i] * PRIME % MOD
		self.prefix = prefix

	def getHash(self, i, j):
		return (self.prefix[j] - self.prefix[i] * cachedPow[j - i]) % MOD

def solve(s):
	n = len(s)
	minAB = 0
	for i in range(n):
		if i < n - 1 - i and s[i] == s[n - 1 - i]:
			minAB = i + 1
		else:
			break
	if minAB == len(s) // 2:
		return s
	forward = RabinKarpRollingHash(s)
	backward = RabinKarpRollingHash(s[::-1])

	def isPalindrome(i, j):
		return forward.getHash(i, j) == backward.getHash(n - j, n - i)
	best = (2 * minAB, minAB, minAB)
	for l in range(n - 2 * minAB, -1, -1):
		if isPalindrome(minAB, minAB + l):
			a = minAB + l
			b = minAB
			best = max(best, (a + b, a, b))
			break
		elif isPalindrome(n - minAB - l, n - minAB):
			a = minAB
			b = minAB + l
			best = max(best, (a + b, a, b))
			break
	(l, a, b) = best
	return s[:a] + s[n - b:]
input = sys.stdin.readline
answers = []
T = int(input())
for t in range(T):
	S = input().rstrip()
	answers.append(solve(S))
print('\n'.join(answers))


t = int(input())

def prefix(s):
	s = s + '#' + s[::-1]
	n = len(s)
	l = [0] * n
	i = 0
	j = 1
	while j < n:
		if i == 0 or s[i] == s[j]:
			l[j] = i + 1
			i += 1
			j += 1
		else:
			i = l[i - 1]
	return l[n - 1]
for _ in range(t):
	s = input()
	n = len(s)
	i = 0
	for i in range(n // 2 + 1):
		if s[i] != s[n - i - 1]:
			break
	ans = i
	a1 = prefix(s[ans:n - ans])
	a2 = prefix(s[ans:n - ans][::-1])
	if a1 >= a2:
		mid = s[ans:ans + a1]
	else:
		mid = s[n - ans - a2:n - ans]
	print(s[:ans] + mid + s[n - ans:])


def pre(s):
	p = s + '#' + s[::-1]
	pi = [0] * len(p)
	j = 0
	for i in range(1, len(p)):
		while j != 0 and p[j] != p[i]:
			j = pi[j - 1]
		if p[j] == p[i]:
			j += 1
		pi[i] = j
	return s[:j]
for _ in range(int(input())):
	s = input()
	l = 0
	while l < len(s) // 2 and s[l] == s[-(l + 1)]:
		l += 1
	pp = pre(s[l:len(s) - l])
	sp = pre(s[l:len(s) - l][::-1])
	pp = pp if len(pp) > len(sp) else sp
	print(s[:l] + pp + s[len(s) - l:])


t = int(input())

def findLongestPalindromicString(text, maxL):
	N = len(text)
	if N == 0:
		return 0
	N = 2 * N + 1
	L = [0] * N
	L[0] = 0
	L[1] = 1
	C = 1
	R = 2
	i = 0
	iMirror = 0
	maxLPSLength = 0
	maxLPSCenterPosition = 0
	start = -1
	end = -1
	diff = -1
	for i in range(2, N):
		iMirror = 2 * C - i
		L[i] = 0
		diff = R - i
		if diff > 0:
			L[i] = min(L[iMirror], diff)
		try:
			while (i + L[i] < N and i - L[i] > 0) and ((i + L[i] + 1) % 2 == 0 or text[(i + L[i] + 1) // 2] == text[(i - L[i] - 1) // 2]):
				L[i] += 1
		except Exception:
			pass
		if L[i] > maxLPSLength:
			maxLPSLength = L[i]
			maxLPSCenterPosition = i
		if i + L[i] > R:
			C = i
			R = i + L[i]
	start_Max = 0
	end_Max = 0
	i = 1
	while i <= maxL:
		if L[i] == i:
			start_Max = i
		if L[N - 1 - i] == i:
			end_Max = i
		i += 1
	if start_Max > end_Max:
		return start_Max
	else:
		return -end_Max
for _ in range(t):
	s = input()
	n = len(s)
	prefix = ''
	suffix = ''
	remaining = s
	ans = 0
	for i in range(n // 2):
		if s[i] == s[n - 1 - i]:
			ans = i + 1
		else:
			break
	if ans != 0:
		prefix = s[0:ans]
		suffix = s[n - ans:n]
		remaining = s[ans:n - ans]
	x = findLongestPalindromicString(remaining, n - 2 * ans)
	temp = ''
	if x == 0:
		pass
	elif x < 0:
		temp = remaining[x:]
	else:
		temp = remaining[:x]
	print(prefix + temp + suffix)


def help(s):
	if s == '':
		return ''
	base = 26
	mod = 86028121
	mod1 = 179424673
	hash1 = 0
	hash2 = 0
	hash11 = 0
	hash22 = 0
	pos = -1
	pow = 1
	pow1 = 1
	for i in range(len(s)):
		hash1 = (hash1 * base + ord(s[i]) - ord('a')) % mod
		hash2 = (hash2 + (ord(s[i]) - ord('a')) * pow) % mod
		hash11 = (hash11 * base + ord(s[i]) - ord('a')) % mod1
		hash22 = (hash22 + (ord(s[i]) - ord('a')) * pow1) % mod1
		if hash1 == hash2 and hash11 == hash22:
			pos = i
		pow = pow * base % mod
		pow1 = pow1 * base % mod1
	return s[:pos + 1]
for _ in range(int(input())):
	s = input()
	n = len(s)
	count = 0
	i = 0
	j = n - 1
	while j > i:
		if s[j] != s[i]:
			break
		count += 1
		i += 1
		j -= 1
	posi1 = help(s[count:n - count])
	posi2 = help(s[count:n - count][::-1])
	print(s[:count] + (posi1 if len(posi1) > len(posi2) else posi2) + s[:count][::-1])


import sys
import math
input = sys.stdin.readline
n = int(input())

def check(s):
	s1 = s + '*' + s[::-1]
	lps = [0] * len(s1)
	for i in range(1, len(lps)):
		j = lps[i - 1]
		while j > 0 and s1[i] != s1[j]:
			j = lps[j - 1]
		k = 0
		if s1[i] == s1[j]:
			k = 1
		lps[i] = j + k
	return s1[:lps[-1]]

def fun(s):
	z1 = check(s)
	z2 = check(s[::-1])
	if len(z1) >= len(z2):
		return z1
	else:
		return z2
for t1 in range(n):
	t = input()
	t = t.strip()
	i = 0
	j = len(t) - 1
	if t[i] == t[j]:
		while i <= j and t[i] == t[j]:
			i += 1
			j -= 1
		i -= 1
		j += 1
		m = ''
		if i + 1 <= j - 1:
			s = t[i + 1:j]
			ans = fun(s)
			m = ans
			if i == j:
				print(t[:i + 1] + m + t[j + 1:])
			else:
				print(t[:i + 1] + m + t[j:])
		elif i == j:
			print(t[:i + 1] + t[j + 1:])
		else:
			print(t[:i + 1] + t[j:])
	else:
		m = fun(t)
		print(m)


class manacher:

	def __init__(self, l):
		self.n = len(l)
		self.m = 2 * self.n + 1
		self.d = ['&'] * self.m
		self.r = [0] * self.m
		for i in range(self.n):
			self.d[2 * i + 1] = l[i]
		self.make_r()

	def make_r(self):
		(i, j) = (0, 0)
		while i < self.m:
			while j <= i < self.m - j and self.d[i - j] == self.d[i + j]:
				j += 1
			self.r[i] = j
			k = 1
			while k <= i < self.m - k and k + self.r[i - k] < j:
				self.r[i + k] = self.r[i - k]
				k += 1
			i += k
			j -= k

	def judge(self, start, end):
		center = start + end
		return 2 * end - 1 < center + self.r[center]
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	s = input().strip()
	n = len(s)
	ll = 0
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			break
		ll += 1
	x = s
	if ll > 0:
		x = s[ll:-ll]
	sss = manacher(x)
	jj = 0
	for i in range(len(x), 0, -1):
		if sss.judge(0, i):
			jj = i
			break
	lll = 0
	for i in range(len(x), 0, -1):
		if sss.judge(len(x) - i, len(x)):
			lll = i
			break
	if lll < jj:
		print(s[:ll] + x[:jj] + s[:ll][::-1])
	else:
		print(s[:ll] + x[::-1][:lll] + s[:ll][::-1])


from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from collections import defaultdict as dd, deque

def data():
	return sys.stdin.readline().strip()

def mdata():
	return map(int, data().split())
mod = 998244353

def computeLPSArray(s):
	pat = s + '.' + s[::-1]
	M = len(pat)
	l = 0
	lps = [0] * M
	i = 1
	while i < M:
		if pat[i] == pat[l]:
			l += 1
			lps[i] = l
			i += 1
		elif l != 0:
			l = lps[l - 1]
		else:
			lps[i] = 0
			i += 1
	return s[:lps[-1]]

def longest(s):
	(a, b) = (computeLPSArray(s), computeLPSArray(s[::-1]))
	return a if len(a) > len(b) else b
for t in range(int(data())):
	s = data()
	n = len(s)
	j = 0
	for i in range(n // 2):
		j = i
		if s[i] != s[n - 1 - i]:
			break
	print(s[:j] + longest(s[j:n - j]) + s[n - j:])


def isPlaindrome(str1):
	n = len(str1)
	for i in range(n // 2):
		if str1[i] != str1[-i - 1]:
			return False
	return True

def function(str1, a):
	temp = str1 + '_'
	str1 = str1[::-1]
	temp = temp + str1
	lis = [0] * (2 * a + 1)
	for i in range(1, 2 * a + 1):
		num = lis[i - 1]
		while num > 0 and temp[num] != temp[i]:
			num = lis[num - 1]
		if temp[i] == temp[num]:
			num += 1
		lis[i] = num
	return temp[0:lis[-1]]
t = int(input())
for _ in range(t):
	s1 = str(input())
	n = len(s1)
	ind = -1
	for i in range(n // 2):
		if s1[i] != s1[-i - 1]:
			ind = i
			break
	if ind == -1:
		print(s1)
	else:
		s = s1[ind:n - ind]
		a = n - ind - ind
		temp1 = function(s, a)
		s = s[::-1]
		temp2 = function(s, a)
		if len(temp1) > len(temp2):
			temp = temp1
		else:
			temp = temp2
		if ind > 0:
			ans = s1[:ind] + temp + s1[-ind:]
		else:
			ans = temp
		print(ans)


from sys import stdin
from bisect import bisect_left as bl
from bisect import bisect_right as br

def input():
	return stdin.readline()[:-1]

def intput():
	return int(input())

def sinput():
	return input().split()

def intsput():
	return map(int, sinput())

class RangedList:

	def __init__(self, start, stop, val=0):
		self.shift = 0 - start
		self.start = start
		self.stop = stop
		self.list = [val] * (stop - start)

	def __setitem__(self, key, value):
		self.list[key + self.shift] = value

	def __getitem__(self, key):
		return self.list[key + self.shift]

	def __repr__(self):
		return str(self.list)

	def __iter__(self):
		return iter(self.list)

def dprint(*args, **kwargs):
	if debugging:
		print(*args, **kwargs)

def prefix_function(x):
	n = len(x)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j > 0 and x[i] != x[j]:
			j = pi[j - 1]
		if x[i] == x[j]:
			j += 1
		pi[i] = j
	return pi[-1]
debugging = 1
t = intput()
for _ in range(t):
	front = []
	back = []
	s = list(input())
	fhead = 0
	bhead = len(s) - 1
	while s[fhead] == s[bhead] and fhead < bhead:
		front.append(s[fhead])
		back.append(s[bhead])
		fhead += 1
		bhead -= 1
	newstring = s[fhead:bhead + 1]
	formatted = newstring + ['*'] + newstring[::-1]
	prefixlength = prefix_function(formatted)
	bestprefix = newstring[:prefixlength]
	newstring = newstring[::-1]
	formatted = newstring + ['*'] + newstring[::-1]
	suffixlength = prefix_function(formatted)
	bestsuffix = newstring[:suffixlength]
	if prefixlength > suffixlength:
		front += bestprefix
	else:
		back += bestsuffix
	print(''.join(front) + ''.join(back[::-1]))


from sys import stdin

def inp():
	return stdin.buffer.readline().rstrip().decode('utf8')

def itg():
	return int(stdin.buffer.readline())

def mpint():
	return map(int, stdin.buffer.readline().split())

def longest_palindromic_prefix(s):
	n = len(s)
	p = [[0] * (n + 1), [0] * n]
	for (z, p_z) in enumerate(p):
		(left, right) = (0, 0)
		for i in range(n):
			t = right - i + 1 - z
			if i < right:
				p_z[i] = min(t, p_z[left + t])
			(L, R) = (i - p_z[i], i + p_z[i] - 1 + z)
			while L >= 1 and R + 1 < n and (s[L - 1] == s[R + 1]):
				p_z[i] += 1
				L -= 1
				R += 1
			if R > right:
				(left, right) = (L, R)
	i1 = x1 = i2 = x2 = 0
	for (i, x) in enumerate(p[0]):
		if i == x and x > x1:
			(i1, x1) = (i, x)
	for (i, x) in enumerate(p[1]):
		if i == x and x > x2:
			(i2, x2) = (i, x)
	return max(s[i1 - x1:i1 + x1], s[i2 - x2:i2 + x2 + 1], key=len)
for case in range(itg()):
	s = inp()
	n = len(s)
	p_len = 0
	for i in range(n >> 1):
		if s[i] == s[-i - 1]:
			p_len = i + 1
		else:
			break
	s_pre = s[:p_len]
	s_suf = s[:p_len][::-1]
	if p_len:
		s = s[p_len:-p_len]
	s_mid = longest_palindromic_prefix(s)
	longest_suffix = longest_palindromic_prefix(s[::-1])
	if len(longest_suffix) > len(s_mid):
		s_mid = longest_suffix
	print(s_pre + s_mid + s_suf)


if 1:

	def lps(r):
		if not r:
			return 0
		r = r + '#' + r[::-1] + '$'
		i = 0
		j = -1
		nt = [0] * len(r)
		nt[0] = -1
		while i < len(r) - 1:
			if j == -1 or r[i] == r[j]:
				i += 1
				j += 1
				nt[i] = j
			else:
				j = nt[j]
		return nt[len(r) - 1]
for tc in range(int(input())):
	s = input()
	if s == s[::-1]:
		print(s)
		continue
	i = 0
	j = len(s) - 1
	aa = ''
	bb = ''
	while s[i] == s[j]:
		i += 1
		j -= 1
	aa = s[:i]
	ii = i
	jj = j
	ss = s[i:j + 1]
	tem = ''
	temp = []
	a = ''
	b = ''
	n = len(ss)
	sss = ss[::-1]
	l1 = lps(ss)
	l2 = lps(sss)
	ma = max(l1, l2)
	h = ss[:ma]
	hh = sss[:ma]
	if h == h[::-1]:
		print(aa + h + aa[::-1])
	else:
		print(aa + hh + aa[::-1])


import os
import io
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce
from collections import deque
import threading

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())
mod = int(1000000000.0) + 7

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def findprefix(s):
	n = len(s)
	prefix = [0] * n
	j = 0
	for i in range(1, n):
		j = prefix[i - 1]
		while j > 0 and s[i] != s[j]:
			j = prefix[j - 1]
		if s[i] == s[j]:
			j += 1
		prefix[i] = j
	return j
for _ in range(iinput()):
	s = list(input())
	n = len(s)
	a = []
	b = []
	(i, j) = (0, n - 1)
	while i < j:
		if s[i] != s[j]:
			break
		a.append(s[i])
		b.append(s[j])
		i += 1
		j -= 1
	if i >= j:
		print(''.join(s))
	else:
		process = s[i:j + 1]
		processrev = process[::-1]
		got1 = findprefix(process + ['#'] + processrev)
		got2 = findprefix(processrev + ['#'] + process)
		toadd = ''
		if got1 > got2:
			toadd = process[:got1]
		else:
			toadd = processrev[:got2]
		print(''.join(a) + ''.join(toadd) + ''.join(b[::-1]))


from sys import stdin, stdout, setrecursionlimit
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log, log2
from random import seed, randint
from datetime import datetime
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
from collections import defaultdict as dd
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def def_value():
	return 0

def def_inf():
	return inf

def atoi(s):
	return ord(s) - ord('a')

def inc(s, n=1):
	return chr((ord(s) - ord('a') + n) % 26 + ord('a'))

class XY:

	def __init__(self, x, y):
		self.x = x
		self.y = y

def rotate(a, b, c):
	ang = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y)
	if ang == 0:
		return 0
	else:
		return ang / abs(ang)
for _ in range(iinp()):
	s = inp()
	(n, k) = (len(s), 0)
	for i in range(n // 2):
		if s[i] != s[n - 1 - i]:
			break
		k += 1
	ss = s[k:n - k]
	sss = ss[::-1]
	temp = ss + '?' + sss
	nn = len(temp)
	lps = l1d(nn, 0)
	for i in range(1, nn):
		ln = lps[i - 1]
		while ln > 0 and temp[ln] != temp[i]:
			ln = lps[ln - 1]
		if temp[i] == temp[ln]:
			ln += 1
		lps[i] = ln
	pre = temp[0:lps[nn - 1]]
	temp = sss + '?' + ss
	lps = l1d(nn, 0)
	for i in range(1, nn):
		ln = lps[i - 1]
		while ln > 0 and temp[ln] != temp[i]:
			ln = lps[ln - 1]
		if temp[i] == temp[ln]:
			ln += 1
		lps[i] = ln
	suf = temp[0:lps[nn - 1]]
	if len(suf) > len(pre):
		print(s[:k] + suf + s[n - k:])
	else:
		print(s[:k] + pre + s[n - k:])


import sys, math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return s[:len(s) - 1]

def invr():
	return map(int, input().split())
t = 1
t = inp()
for tt in range(t):
	a = insr()
	n = len(a)
	for i in range(len(a) // 2 + 1):
		if i < n - i - 1:
			if a[i] != a[n - i - 1]:
				break
	qwqw = i
	qw = a[i:n - i]
	if len(qw) == 0:
		print(a[:i] + a[n - i:])
	else:
		q = qw + ' ' + ''.join(reversed(qw))
		w = ''.join(reversed(qw)) + ' ' + qw
		qq = [0] * len(q)
		ww = [0] * len(w)
		for i in range(1, len(q)):
			qp = qq[i - 1]
			while qp > 0 and q[i] != q[qp]:
				qp = qq[qp - 1]
			qq[i] = qp + (1 if q[i] == q[qp] else 0)
		for i in range(1, len(w)):
			wp = ww[i - 1]
			while wp > 0 and w[i] != w[wp]:
				wp = ww[wp - 1]
			ww[i] = wp + (1 if w[i] == w[wp] else 0)
		qq = qq.pop()
		ww = ww.pop()
		if qq > ww:
			print(a[:qwqw] + q[:qq] + a[n - qwqw:])
		else:
			print(a[:qwqw] + w[:ww] + a[n - qwqw:])


class Solution:

	def manacher(self, s0: str) -> list:
		T = '$#' + '#'.join(s0) + '#@'
		l = len(T)
		P = [0] * l
		(R, C) = (0, 0)
		for i in range(1, l - 1):
			if i < R:
				P[i] = min(P[2 * C - i], R - i)
			while T[i + (P[i] + 1)] == T[i - (P[i] + 1)]:
				P[i] += 1
			if P[i] + i > R:
				R = P[i] + i
				C = i
		for i in reversed(range(len(P))):
			if P[i] > 0:
				start = (i - P[i]) // 2
				if start == 0:
					return s0[0:start + P[i]]

	def shortestPalindrome(self, s: str) -> str:
		if s == '':
			return ''
		return self.manacher(s)
slv = Solution()
n = int(input())
while n != 0:
	n -= 1
	s = input()
	l = len(s)
	L = 0
	R = l - 1
	while L < R:
		if s[L] == s[R]:
			L += 1
			R -= 1
		else:
			break
	if L < R:
		ss = s[L:R + 1]
		ss1 = slv.shortestPalindrome(ss)
		ss2 = slv.shortestPalindrome(''.join(list(reversed(ss))))
		if len(ss2) > len(ss1):
			ss1 = ss2
		print(s[:L] + ss1 + s[R + 1:])
	else:
		print(s)


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	S = input().rstrip()
	N = len(S)
	L = 0
	R = N - 1
	while L < R and S[L] == S[R]:
		L += 1
		R -= 1
	if L == R:
		print(S)
		continue
	SUB = S[L:R + 1]
	M = len(SUB)
	fail1 = [0] * M
	j = 0
	for i in range(1, M):
		while j > 0 and SUB[i] != SUB[j]:
			j = fail1[j - 1]
		if SUB[i] == SUB[j]:
			j += 1
			fail1[i] = j
	SUB2 = SUB[::-1]
	fail2 = [0] * M
	j = 0
	for i in range(1, M):
		while j > 0 and SUB2[i] != SUB2[j]:
			j = fail2[j - 1]
		if SUB2[i] == SUB2[j]:
			j += 1
			fail2[i] = j
	j = 0
	for i in range(M):
		while j > 0 and SUB[i] != SUB2[j]:
			j = fail2[j - 1]
		if SUB[i] == SUB2[j]:
			j += 1
	ans1 = S[:L] + S[R - j + 1:R + 1] + S[R + 1:]
	j = 0
	for i in range(M):
		while j > 0 and SUB2[i] != SUB[j]:
			j = fail1[j - 1]
		if SUB2[i] == SUB[j]:
			j += 1
	ans2 = S[:L] + S[L:L + j] + S[R + 1:]
	if len(ans1) < len(ans2):
		print(ans2)
	else:
		print(ans1)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def longestPalindromicPrefix(Str):
	temp = Str + '?'
	Str = Str[::-1]
	temp = temp + Str
	n = len(temp)
	lps = [0] * n
	for i in range(1, n):
		Len = lps[i - 1]
		while Len > 0 and temp[Len] != temp[i]:
			Len = lps[Len - 1]
		if temp[i] == temp[Len]:
			Len += 1
		lps[i] = Len
	return lps[n - 1]
allAns = []
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	maxDepth = 0
	for i in range(n // 2):
		if s[i] == s[n - 1 - i]:
			maxDepth += 1
		else:
			break
	start = s[:maxDepth]
	end = start[::-1]
	if maxDepth > 0:
		s2 = s[maxDepth:-maxDepth]
	else:
		s2 = s
	x1 = longestPalindromicPrefix(s2)
	ans1 = start + s2[:x1] + end
	s3 = s2[::-1]
	x2 = longestPalindromicPrefix(s3)
	ans2 = start + s3[:x2] + end
	ans2 = ans2[::-1]
	if len(ans1) > len(ans2):
		allAns.append(ans1)
	else:
		allAns.append(ans2)
multiLineArrayPrint(allAns)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	(l, r) = (0, n - 1)
	for i in range(n):
		if i < n - 1 - i and s[i] == s[n - 1 - i]:
			(l, r) = (i + 1, n - 1 - (i + 1))
			continue
		break
	(pref, s, post) = (s[:l], s[l:r + 1], s[r + 1:])
	if not s:
		print(pref + post)
	else:
		n = len(s)
		d1 = [0] * n
		(l, r) = (0, -1)
		m = 0
		best = (0, 0)
		for i in range(n):
			k = 1 if i > r else min(d1[l + r - i], r - i + 1)
			while i + k < n and i - k >= 0 and (s[i + k] == s[i - k]):
				k += 1
			d1[i] = k
			if i + k - 1 > r:
				(l, r) = (i - k + 1, i + k - 1)
			w = 1 + (k - 1) * 2
			if m < w:
				if k - 1 == i:
					m = w
					best = (0, i + k)
				elif n - k == i:
					m = w
					best = (i - (k - 1), n)
		d2 = [0] * n
		(l, r) = (0, -1)
		for i in range(n):
			k = 0 if i > r else min(d2[l + r - i + 1], r - i + 1)
			while i + k < n and i - k - 1 >= 0 and (s[i + k] == s[i - k - 1]):
				k += 1
			d2[i] = k
			if i + k - 1 > r:
				(l, r) = (i - k, i + k - 1)
			w = k * 2
			if m < w:
				if k == i:
					m = w
					best = (0, i + k)
				elif n - k == i:
					m = w
					best = (i - k, n)
		print(pref + s[best[0]:best[1]] + post)


import math
import sys
from collections import defaultdict, Counter, deque, OrderedDict
import bisect
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]
from itertools import accumulate, groupby
import sys
mod = 1000000007

def lpx(pat, patt):
	pat = pat + '#' + patt
	lenpat = len(pat)
	lps = [0] * lenpat
	l = 0
	i = 1
	while i < lenpat:
		if pat[i] == pat[l]:
			l += 1
			lps[i] = l
			i += 1
		elif l != 0:
			l = lps[l - 1]
		else:
			lps[i] = 0
			i += 1
	return lps[-1]

def findmax(S):
	i = 0
	j = len(S) - 1
	s = ''
	while i <= j:
		if S[i] == S[j]:
			s += S[i]
		else:
			return s
		i += 1
		j -= 1
	return s
for _ in range(int(input())):
	S = input()
	N = len(S)
	if N == 1:
		print(S)
	else:
		x = findmax(S)
		y = len(x)
		if N % 2 == 0:
			if y * 2 == N:
				print(S)
				continue
		elif y * 2 == N + 1:
			print(S)
			continue
		T = S[y:N - y]
		TT = T[::-1]
		t = lpx(T, TT)
		u = lpx(TT, T)
		if t > u:
			print(x + T[:t] + S[N - y:])
		else:
			print(x + T[len(T) - u:] + S[N - y:])


def getLPSFromIEq0_len(text):
	N = len(text)
	if N == 0:
		return
	N = 2 * N + 1
	L = [0] * N
	L[0] = 0
	L[1] = 1
	C = 1
	R = 2
	i = 0
	iMirror = 0
	maxLPSLength = 0
	maxLPSCenterPosition = 0
	start = -1
	end = -1
	diff = -1
	lpsFromIEq0Len = 1
	for i in range(2, N):
		iMirror = 2 * C - i
		L[i] = 0
		diff = R - i
		if diff > 0:
			L[i] = min(L[iMirror], diff)
		try:
			while (i + L[i] < N and i - L[i] > 0) and ((i + L[i] + 1) % 2 == 0 or text[(i + L[i] + 1) // 2] == text[(i - L[i] - 1) // 2]):
				L[i] += 1
		except Exception as e:
			pass
		if L[i] > maxLPSLength:
			maxLPSLength = L[i]
			maxLPSCenterPosition = i
		if i == L[i]:
			lpsFromIEq0Len = max(lpsFromIEq0Len, L[i])
		if i + L[i] > R:
			C = i
			R = i + L[i]
	return lpsFromIEq0Len

def main():
	q = int(input())
	allans = []
	for _ in range(q):
		s = input()
		i = 0
		j = len(s) - 1
		while i <= j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			else:
				break
		if i > j:
			allans.append(s)
			continue
		middleS = s[i:j + 1]
		l1 = getLPSFromIEq0_len(middleS)
		l2 = getLPSFromIEq0_len(middleS[::-1])
		if l1 >= l2:
			innerPalindrome = middleS[:l1]
		else:
			innerPalindrome = middleS[-l2:]
		ans = s[:i] + innerPalindrome + s[j + 1:]
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
from functools import lru_cache
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
if os.path.exists('out.txt'):
	sys.stdout = open('out.txt', 'w')

def input():
	return sys.stdin.readline()

def mapi(arg=0):
	return map(int if arg == 0 else str, input().split())
for _ in range(int(input())):
	a = input().strip()
	n = len(a)
	i = 0
	j = n - 1
	while i < j:
		if a[i] == a[j]:
			i += 1
			j -= 1
		else:
			break
	pf = list(a[:i])
	sf = list(a[j + 1:])
	a = a[i:j + 1]
	prep = []
	prep.append('#')
	for i in range(len(a)):
		prep.append(a[i])
		prep.append('#')
	n = len(prep)
	left = [0] * n
	(r, c) = (0, 0)
	for i in range(n):
		mirror = 2 * c - i
		if r > i:
			left[i] = min(r - i, left[mirror])
		while i + left[i] + 1 < n and i - left[i] - 1 >= 0 and (prep[i + left[i] + 1] == prep[i - left[i] - 1]):
			left[i] += 1
		if i + left[i] > r:
			c = i
			r = i + left[i]
	mxlen = 0
	center = 0
	for i in range(n):
		if left[i] > mxlen and (i == left[i] or i + left[i] >= n - 1):
			mxlen = left[i]
			center = i
	res = []
	for i in prep[center - mxlen:center + mxlen + 1]:
		if i == '#':
			continue
		res.append(i)
	res = pf + res + sf
	print(*res, sep='')


def Z_Array(l):
	left = 0
	right = 0
	n = len(l)
	Z = [0] * n
	for i in range(1, n):
		if i > right:
			left = i
			right = i
			while right < n and l[right] == l[right - left]:
				right += 1
			Z[i] = right - left
			right -= 1
		else:
			k = i - left
			if Z[k] + i - 1 < right:
				Z[i] = Z[k]
			else:
				left = i
				while right < n and l[right] == l[right - left]:
					right += 1
				Z[i] = right - left
				right -= 1
	return Z

def Z_Algorithm(pattern, text):
	l = [p for p in pattern]
	l.append('#')
	l.extend([t for t in text])
	Z = Z_Array(l)
	return Z

def maximum_Length_Palindrome(Z, n):
	for i in range(n):
		if Z[i] == n - i:
			return Z[i]
for _ in range(int(input())):
	s = input()
	n = len(s)
	N = 2 * n + 1
	if n == 1 or s == s[::-1]:
		print(s)
	elif s[0] != s[-1]:
		ans1 = Z_Algorithm(s, s[::-1])
		ans2 = Z_Algorithm(s[::-1], s)
		ans1 = maximum_Length_Palindrome(ans1[N // 2 + 1:], n)
		ans2 = maximum_Length_Palindrome(ans2[N // 2 + 1:], n)
		if ans1 >= ans2:
			print(s[:ans1])
		else:
			s = s[::-1]
			print(s[:ans2])
	else:
		i = 0
		j = n - 1
		s1 = s[0:n]
		while i < j:
			if s[i] != s[j]:
				break
			else:
				i += 1
				j -= 1
		s = s[i:j + 1]
		n = len(s)
		N = 2 * n + 1
		ans1 = Z_Algorithm(s, s[::-1])
		ans2 = Z_Algorithm(s[::-1], s)
		ans1 = maximum_Length_Palindrome(ans1[N // 2 + 1:], n)
		ans2 = maximum_Length_Palindrome(ans2[N // 2 + 1:], n)
		if ans1 >= ans2:
			s = s[:ans1]
			if s == s[::-1]:
				print(s1[0:i] + s[:ans1] + s1[0:i][::-1])
		else:
			s = s[::-1]
			s = s[:ans2]
			if s == s[::-1]:
				print(s1[0:i] + s[:ans2] + s1[0:i][::-1])


def solve_palindrome(pat):
	pat += '#' + pat[::-1]
	lps = [0] * len(pat)
	length = 0
	i = 1
	while i < len(pat):
		if pat[i] == pat[length]:
			length += 1
			lps[i] = length
			i += 1
		elif length != 0:
			length = lps[length - 1]
		else:
			lps[i] = 0
			i += 1
	return pat[0:lps[len(pat) - 1]]

def solve():
	a = input()
	b = a[::-1]
	j = 0
	while a[j] == b[j] and j * 2 < len(a) - 1:
		j += 1
	c = a[:j]
	b = b[j:len(b) - j]
	a = a[j:len(a) - j]
	aa = solve_palindrome(a)
	bb = solve_palindrome(b)
	if len(aa) < len(bb):
		aa = bb
	print(c + aa + c[::-1])
n = int(input())
for i in range(n):
	solve()


import sys

def longest_pal(s):
	kmp = s + '#' + s[::-1]
	lps = [0] * len(kmp)
	n1 = len(kmp)
	for i in range(1, n1):
		prev_idx = lps[i - 1]
		while prev_idx > 0 and kmp[i] != kmp[prev_idx]:
			prev_idx = lps[prev_idx - 1]
		if kmp[i] == kmp[prev_idx]:
			lps[i] = prev_idx + 1
		else:
			lps[i] = prev_idx
	return lps[n1 - 1]
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	(i, j, maxi) = (0, n - 1, 0)
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
			maxi += 1
		else:
			break
	if maxi > 0:
		print(s[:i], end='')
	if 2 * maxi != n:
		maxi3 = longest_pal(s[i:j + 1])
		s1 = s[i:j + 1]
		maxi4 = longest_pal(s1[::-1])
		if maxi3 > maxi4:
			print(s[i:i + maxi3], end='')
		else:
			print(s[j + 1 - maxi4:j + 1], end='')
	if maxi > 0:
		print(s[j + 1:])
	else:
		print()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for ti in range(int(input())):
	s_o = input()
	revl = 0
	for (j, jitm) in enumerate(s_o):
		if jitm == s_o[-j - 1] and j < len(s_o) >> 1:
			revl += 1
		else:
			break
	revs = s_o[:revl]
	if len(s_o) >> 1 <= revl:
		print(s_o)
		continue
	ans = ''
	if revl:
		s_o = s_o[revl:-revl]
	s = '^#' + '#'.join(list(s_o)) + '#$'
	p = []
	mx = 0
	_id = 0
	br1 = 0
	br2 = 0
	for (idx, i) in enumerate(s):
		if idx < mx:
			p.append(min(p[2 * _id - idx], mx - idx))
		else:
			p.append(1)
		while idx + p[idx] < len(s) and s[idx - p[idx]] == s[idx + p[idx]]:
			p[idx] += 1
		if mx < idx + p[idx]:
			_id = idx
			mx = idx + p[idx]
		_tmp = p[idx] - 1
		if p[idx] - 1 & 1:
			r1 = (idx >> 1) - (_tmp >> 1) - 1
			r2 = (idx >> 1) + (_tmp >> 1)
		else:
			r1 = (idx >> 1) - (_tmp >> 1)
			r2 = (idx >> 1) + (_tmp >> 1)
		if idx > 0 and i != '$':
			if (r1 == 0 or r2 == len(s_o)) and r2 - r1 > br2 - br1:
				br1 = r1
				br2 = r2
	print(revs + s_o[br1:br2] + revs[::-1])


import sys
for _ in range(int(input())):
	s = input()
	p = ''
	(i, j) = (0, len(s) - 1)
	while i <= j and s[i] == s[j]:
		i += 1
		j -= 1
	if i > j:
		print(s)
	else:
		p = s[:i]
		s = s[i:j + 1]

		def manacher(ms):
			ms = '$#' + '#'.join(ms) + '#%'
			l = len(ms)
			p = [0] * len(ms)
			ind = mx = 0
			ans = 0
			for i in range(1, l - 1):
				if i < mx:
					p[i] = min(p[2 * ind - i], mx - i)
				while ms[i - p[i] - 1] == ms[i + p[i] + 1]:
					p[i] += 1
				if mx < i + p[i]:
					(ind, mx) = (i, i + p[i])
				if i - p[i] == 1 and p[i] > abs(ans):
					ans = p[i]
				if i + p[i] == l - 2 and p[i] > abs(ans):
					ans = -p[i]
			if ans > 0:
				return s[:ans]
			else:
				return s[ans:]
		t = manacher(s)
		print(p + t + p[::-1])


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

def gift():
	for _ in range(t):
		string = input()
		n = len(string)
		if n == 1:
			yield string[0]
		else:
			(s, e) = (0, n - 1)
			while s < e:
				if string[s] == string[e]:
					s += 1
					e -= 1
				else:
					break
			form = [string[:s]]
			back = [string[e + 1:]]
			srem = string[s:e + 1]
			mid = ['']
			for i in srem:
				mid.append(i)
				mid.append('')
			R = [None] * len(mid)
			i = 0
			j = 0
			while i < len(mid):
				while i - j >= 0 and i + j < len(mid) and (mid[i - j] == mid[i + j]):
					j += 1
				R[i] = j
				k = 1
				while i - k >= 0 and i + k < len(mid) and (k + R[i - k] < j):
					R[i + k] = R[i - k]
					k += 1
				i += k
				j -= k
			maxind = 0
			for i in range(len(mid)):
				if (i + 1 == R[i] or R[i] == len(mid) - i) and R[maxind] < R[i]:
					maxind = i
			for i in range(maxind - R[maxind] + 1, maxind + R[maxind]):
				form.append(mid[i])
			ans = form + back
			yield ''.join(ans)
t = int(input())
ans = gift()
print(*ans, sep='\n')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())

def longest_palindrome_prefix(s):
	if not s:
		return 0
	s = s + '#' + s[::-1] + '$'
	i = 0
	j = -1
	nt = [0] * len(s)
	nt[0] = -1
	while i < len(s) - 1:
		if j == -1 or s[i] == s[j]:
			i += 1
			j += 1
			nt[i] = j
		else:
			j = nt[j]
	return nt[len(s) - 1]
for _ in range(n):
	s = input()
	left = 0
	right = len(s) - 1
	while left <= right:
		if s[left] == s[right]:
			left += 1
			right -= 1
		else:
			break
	if left > right:
		print(s)
		continue
	(pref, suff) = (s[:left], s[right + 1:])
	cut = s[left:right + 1]
	longest_left = cut[:longest_palindrome_prefix(cut)]
	cut = cut[::-1]
	longest_right = cut[:longest_palindrome_prefix(cut)]
	longest_right = longest_right[::-1]
	if len(longest_left) > len(longest_right):
		print(pref + longest_left + suff)
	else:
		print(pref + longest_right + suff)


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def Manacher(S):
	N = len(S)
	R = [0] * N
	i = j = 0
	while i < N:
		while i - j >= 0 and i + j < N and (S[i - j] == S[i + j]):
			j += 1
		R[i] = j
		k = 1
		while i - k >= 0 and i + k < N and (k + R[i - k] < j):
			R[i + k] = R[i - k]
			k += 1
		i += k
		j -= k
	return R

def Manacher_even(_S):
	_N = len(_S)
	S = []
	for i in range(_N - 1):
		S.append(_S[i])
		S.append('$')
	S.append(_S[-1])
	N = len(S)
	R = [0] * N
	i = j = 0
	while i < N:
		while i - j >= 0 and i + j < N and (S[i - j] == S[i + j]):
			j += 1
		R[i] = j
		k = 1
		while i - k >= 0 and i + k < N and (k + R[i - k] < j):
			R[i + k] = R[i - k]
			k += 1
		i += k
		j -= k
	res = [0] * (_N - 1)
	j = 0
	for i in range(1, N, 2):
		res[j] = R[i] // 2
		j += 1
	return res
for _ in range(INT()):
	S = input()
	N = len(S)
	i = 0
	j = N - 1
	T1 = []
	while i < j:
		if S[i] == S[j]:
			T1.append(S[i])
			i += 1
			j -= 1
		else:
			break
	else:
		print(S)
		continue
	T3 = T1[::-1]
	R = Manacher(S[i:j + 1])
	mx = a = b = 0
	for (k, r) in enumerate(R):
		k += i
		ln = r * 2 - 1
		if k - r + 1 == i:
			if ln > mx:
				mx = ln
				(a, b) = (i, i + ln)
		if k + r - 1 == j:
			if ln > mx:
				mx = ln
				(a, b) = (j + 1 - ln, j + 1)
	R = Manacher_even(S[i:j + 1])
	for (k, r) in enumerate(R):
		k += i + 1
		ln = r * 2
		if k - r == i:
			if ln > mx:
				mx = ln
				(a, b) = (i, i + ln)
		if k + r - 1 == j:
			if ln > mx:
				mx = ln
				(a, b) = (j + 1 - ln, j + 1)
	T2 = list(S[a:b])
	ans = T1 + T2 + T3
	print(''.join(ans))


from sys import stdin

def inp():
	return stdin.buffer.readline().rstrip().decode('utf8')

def itg():
	return int(stdin.buffer.readline())

def mpint():
	return map(int, stdin.buffer.readline().split())

def longest_prefix(a):
	a = a + '#' + a[::-1]
	pref = [0] * len(a)
	c = 0
	for i in range(1, len(a)):
		while c > 0 and a[c] != a[i]:
			c = pref[c - 1]
		if a[c] == a[i]:
			c += 1
		pref[i] = c
	return a[:c]
for case in range(itg()):
	s = inp()
	n = len(s)
	k = 0
	for i in range(n >> 1):
		if s[i] == s[-i - 1]:
			k = i + 1
		else:
			break
	prefix = s[:k]
	suffix = s[:k][::-1]
	if k:
		s = s[k:-k]
	mid = max(longest_prefix(s), longest_prefix(s[::-1]), key=len)
	print(prefix + mid + suffix)


import sys
input = lambda : sys.stdin.readline().strip()
for i in range(int(input())):
	s = list(input())
	n = len(s)
	ans = -1
	nat = n
	for i in range(n // 2):
		if s[i] != s[-i - 1]:
			ans = i
			break
	if ans == -1:
		print(''.join(map(str, s)))
		continue
	an = s[:ans]
	s = s[ans:n - ans]
	n -= 2 * ans
	d2 = [0] * n
	l = 0
	r = -1
	for i in range(n):
		if i > r:
			k = 0
		else:
			k = min(d2[l + r - i + 1], r - i + 1)
		while i + k < n and i - k - 1 >= 0 and (s[i + k] == s[i - k - 1]):
			k += 1
		d2[i] = k
		if i + k - 1 > r:
			l = i - k
			r = i + k - 1
	d1 = [0] * n
	l = 0
	r = -1
	for i in range(n):
		if i > r:
			k = 1
		else:
			k = min(d1[l + r - i], r - i + 1)
		while i + k < n and i - k >= 0 and (s[i + k] == s[i - k]):
			k += 1
		d1[i] = k
		if i + k - 1 > r:
			l = i - k + 1
			r = i + k - 1
	an1 = 0
	an2 = 0
	an3 = 0
	an4 = 0
	for i in range(n):
		if d1[i] == i + 1:
			an1 = i + 1
		if d2[i] == i:
			an2 = i
		if d1[i] == n - i:
			an3 = max(d1[i], an3)
		if d2[i] == n - i:
			an4 = max(d2[i], an4)
	a = max(an1 * 2 - 1, an2 * 2, an3 * 2 - 1, an4 * 2)
	if a == an1 * 2 - 1:
		ans = an + s[:an1 * 2 - 1] + an[::-1]
	elif a == 2 * an2:
		ans = an + s[:an2 * 2] + an[::-1]
	elif a == an3 * 2 - 1:
		ans = an + s[n - an3 * 2 + 1:] + an[::-1]
	else:
		ans = an + s[n - an4 * 2:] + an[::-1]
	print(''.join(map(str, ans)))


import sys
LI = lambda : list(map(int, sys.stdin.readline().strip('\n').split()))
MI = lambda : map(int, sys.stdin.readline().strip('\n').split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline().strip('\n'))
for _ in range(II()):
	_s = list(SI())
	(t, ans, l, r) = (-1, '', 0, len(_s) - 1)
	while l < r and _s[l] == _s[r]:
		t += 1
		l += 1
		r -= 1
	if r - l >= 0:
		n = (r - l + 1) * 2 + 1
		s = ['#'] * n
		for i in range(n):
			if i & 1:
				s[i] = _s[l]
				l += 1
		(lsp, c, r, lindv, rindv) = ([0] * n, 0, 0, 0, 0)
		for i in range(n):
			mirror = 2 * c - i
			if i < r:
				lsp[i] = min(r - i, lsp[mirror])
			(a, b) = (i + 1 + lsp[i], i - 1 - lsp[i])
			while a < n and b >= 0 and (s[a] == s[b]):
				lsp[i] += 1
				a += 1
				b -= 1
			if i + lsp[i] > r:
				(c, r) = (i, i + lsp[i])
			if i - lsp[i] <= 0 and lsp[i] > lindv:
				lind = i
				lindv = lsp[i]
			if i + lsp[i] >= n - 1 and lsp[i] > rindv:
				rind = i
				rindv = lsp[i]
		if lsp[lind] > lsp[rind]:
			ind = lind
		else:
			ind = rind
		ans = ''.join(list(filter(lambda x: x != '#', s[ind - lsp[ind]:ind + 1] + s[ind + 1:ind + lsp[ind] + 1])))
	at = ''.join(_s[:t + 1])
	print(at + ans + at[::-1])


import sys
input = sys.stdin.readline
print = sys.stdout.write

def isPalindrome(pat):
	pat = pat + '#' + pat[::-1]
	lenpat = len(pat)
	lps = [0] * lenpat
	l = 0
	i = 1
	while i < lenpat:
		if pat[i] == pat[l]:
			l += 1
			lps[i] = l
			i += 1
		elif l != 0:
			l = lps[l - 1]
		else:
			lps[i] = 0
			i += 1
	return lps[-1]
for _ in range(int(input())):
	s = input()[:-1]
	l = len(s)
	a = ''
	b = ''
	(ai, bi) = (0, 0)
	idx = None
	for i in range(l // 2):
		if s[i] == s[l - i - 1]:
			ai += 1
			bi += 1
		else:
			idx = i
			break
	else:
		ans = s
	if idx != None:
		(a, b) = (s[:ai], s[l - bi:])
		ai = None
		bi = None
		temp = s[idx:l - idx]
		ai = isPalindrome(temp)
		bi = isPalindrome(temp[::-1])
		if ai > bi:
			ans = a + temp[:ai] + b
		else:
			ans = a + temp[l - 2 * idx - bi:] + b
	print(ans + '\n')


def LPS(s):
	s = s + '#' + s[::-1]
	n = len(s)
	dp = [0] * n
	j = 0
	i = 1
	while i < n:
		if s[i] == s[j]:
			dp[i] = j + 1
			i += 1
			j += 1
		elif j != 0:
			j = dp[j - 1]
		else:
			dp[i] = 0
			i += 1
	return s[:dp[-1]]
for _ in range(int(input())):
	s = input()
	l = 0
	n = len(s)
	while l < n // 2 and s[l] == s[-(l + 1)]:
		l += 1
	pp = LPS(s[l:n - l])
	ss = LPS(s[l:n - l][::-1])
	if len(ss) > len(pp):
		print(s[:l] + ss + s[:l][::-1])
	else:
		print(s[:l] + pp + s[:l][::-1])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))

def expand(s, left, right):
	while left >= 0 and right < len(s) and (s[left] == s[right]):
		left -= 1
		right += 1
	return (right - left - 2) // 2

def longestPalindrome(s):
	(end, start) = (-1, 0)
	s = '#' + '#'.join(list(s)) + '#'
	arm_len = []
	right = -1
	j = -1
	for i in range(len(s)):
		if right >= i:
			i_sym = 2 * j - i
			min_arm_len = min(arm_len[i_sym], right - i)
			cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len)
		else:
			cur_arm_len = expand(s, i, i)
		arm_len.append(cur_arm_len)
		if i + cur_arm_len > right:
			j = i
			right = i + cur_arm_len
		if 2 * cur_arm_len + 1 > end - start:
			start = i - cur_arm_len
			end = i + cur_arm_len
	return arm_len
for _ in range(N()):
	s = input()
	n = len(s)
	dd = longestPalindrome(s)
	if s == s[::-1]:
		print(s)
	else:
		tail = 0
		while s[tail] == s[n - 1 - tail]:
			tail += 1
		if tail > 0:
			ans = s[:tail] + s[-tail:]
		for m in range(n - 2 >> 1, tail - 1, -1):
			if s[m] == s[m + 1] and (dd[2 * m + 2] >> 1) + tail > m:
				ans = s[:2 * m + 2 - tail] + s[:tail][::-1]
				break
			if (dd[2 * m + 1] >> 1) + tail >= m:
				ans = s[:2 * m + 1 - tail] + s[:tail][::-1]
				break
		k = len(ans)
		for m in range(n + 1 >> 1, n - tail):
			if (n - m) * 2 <= k:
				break
			if s[m] == s[m - 1] and (dd[2 * m] >> 1) + tail >= n - m:
				ans = s[:tail] + s[2 * m - n + tail:]
				break
			if (dd[2 * m + 1] >> 1) + tail + m >= n - 1:
				ans = s[:tail] + s[2 * m - n + tail + 1:]
				break
		print(ans)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	if n == 1:
		print(s)
	else:
		(l_my, r_my) = (0, n - 1)
		while l_my + 1 < r_my - 1 and s[l_my] == s[r_my]:
			l_my += 1
			r_my -= 1
		d1 = [0 for i in range(n)]
		(l, r) = (0, -1)
		for i in range(n):
			if i > r:
				k = 1
			else:
				k = min(d1[l + r - i], r - i + 1)
			while i + k < n and i - k >= 0 and (s[i + k] == s[i - k]):
				k += 1
			d1[i] = k
			if i + k - 1 > r:
				l = i - k + 1
				r = i + k - 1
		d2 = [0 for i in range(n)]
		(l, r) = (0, -1)
		for i in range(n):
			if i > r:
				k = 0
			else:
				k = min(d2[l + r - i + 1], r - i + 1)
			while i + k < n and i - k - 1 >= 0 and (s[i + k] == s[i - k - 1]):
				k += 1
			d2[i] = k
			if i + k - 1 > r:
				l = i - k
				r = i + k - 1
		added = 0
		center_piece = []
		for center in range(l_my, r_my):
			if center - d1[center] < l_my or center + d1[center] > r_my:
				offset = min(d1[center], center - l_my + 1, r_my - center + 1)
				if 2 * (offset - 1) + 1 >= added:
					added = 2 * (offset - 1) + 1
					center_piece = [center - offset + 1, center + offset - 1]
		for center2 in range(l_my + 1, r_my + 1):
			center1 = center2 - 1
			offset = min(d2[center2], center1 - l_my + 1, r_my - center2 + 1)
			if center1 - offset < l_my or center2 + offset > r_my:
				if 2 * (offset - 1) + 2 >= added:
					added = 2 * (offset - 1) + 2
					center_piece = [center1 - offset + 1, center2 + offset - 1]
		print(s[:l_my] + s[center_piece[0]:center_piece[1] + 1] + s[r_my + 1:])


def manacher(S):
	(i, j, n) = (0, 0, len(S))
	R = [0] * n
	while i < n:
		while i - j >= 0 and i + j < n and (S[i - j] == S[i + j]):
			j += 1
		R[i] = j
		k = 1
		while i - k >= 0 and i + k < n and (k + R[i - k] < j):
			R[i + k] = R[i - k]
			k += 1
		i += k
		j -= k
	return R
T = int(input())
for _ in range(T):
	s = input()
	N = len(s)
	idx_s = 0
	for idx_s in range(N // 2):
		if s[idx_s] != s[-1 - idx_s]:
			break
	else:
		print(s)
		continue
	pre = idx_s
	s2 = [s[idx_s]]
	for c in s[idx_s + 1:-idx_s] if idx_s != 0 else s[1:]:
		s2.append('$')
		s2.append(c)
	man = manacher(s2)
	ma_l = 1
	for (idx_man, m) in enumerate(man, 1):
		if m == idx_man:
			ma_l = m
	ma_r = 1
	for (idx_man, m) in enumerate(man[::-1], 1):
		if m == idx_man:
			ma_r = m
	ans = s[:pre] + (s[pre:pre + ma_l] if ma_l > ma_r else s[-pre - ma_r:N - pre]) + (s[-pre:] if pre > 0 else '')
	print(ans)


import sys, heapq as h
input = sys.stdin.readline

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input().strip()

def listStr():
	return list(input().strip())
import collections as col
import math

def longest_prefix_suffix_palindrome(S, N):
	i = -1
	while i + 1 <= N - i - 2 and S[i + 1] == S[N - i - 2]:
		i += 1
	return i

def longest_palindromic_prefix(S):
	tmp = S + '?'
	S = S[::-1]
	tmp = tmp + S
	N = len(tmp)
	lps = [0] * N
	for i in range(1, N):
		L = lps[i - 1]
		while L > 0 and tmp[L] != tmp[i]:
			L = lps[L - 1]
		if tmp[i] == tmp[L]:
			L += 1
		lps[i] = L
	return tmp[:lps[N - 1]]

def solve():
	S = getStr()
	N = len(S)
	i = longest_prefix_suffix_palindrome(S, N)
	if i >= N // 2 - 1:
		return S
	new_str = S[i + 1:N - i - 1]
	longest_pref = longest_palindromic_prefix(new_str)
	longest_suff = longest_palindromic_prefix(new_str[::-1])[::-1]
	add_on = longest_pref if len(longest_pref) >= len(longest_suff) else longest_suff
	return S[:i + 1] + add_on + S[N - i - 1:]
for _ in range(getInt()):
	print(solve())


qn = int(input())
for loop in range(qn):
	s = list(input())
	n = len(s)
	lastif = None
	for i in range((n + 1) // 2):
		if s[i] == s[-1 - i]:
			continue
		else:
			lastif = i
			break
	if lastif == None:
		print(''.join(s))
		continue
	form = s[:lastif]
	back = s[n - lastif:]
	midsub = s[lastif:n - lastif]
	mid = ['']
	for i in midsub:
		mid.append(i)
		mid.append('')
	R = [None] * len(mid)
	i = 0
	j = 0
	while i < len(mid):
		while i - j >= 0 and i + j < len(mid) and (mid[i - j] == mid[i + j]):
			j += 1
		R[i] = j
		k = 1
		while i - k >= 0 and i + k < len(mid) and (k + R[i - k] < j):
			R[i + k] = R[i - k]
			k += 1
		i += k
		j -= k
	maxind = 0
	for i in range(len(mid)):
		if (i + 1 == R[i] or R[i] == len(mid) - i) and R[maxind] < R[i]:
			maxind = i
	for i in range(maxind - R[maxind] + 1, maxind + R[maxind]):
		form.append(mid[i])
	ans = form + back
	print(''.join(ans))


import sys
import math
from collections import defaultdict, deque
import heapq

def kmp(s):
	n = len(s)
	lps = [0 for _ in range(n)]
	l = 0
	lps[0] = 0
	i = 1
	while i < n:
		if s[i] == s[l]:
			l += 1
			lps[i] = l
			i += 1
		elif l != 0:
			l = lps[l - 1]
		else:
			lps[i] = 0
			i += 1
	return lps[-1]
t = int(sys.stdin.readline())
for _ in range(t):
	s = sys.stdin.readline()[:-1]
	n = len(s)
	(i, j) = (0, n - 1)
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			break
	left = s[:i]
	right = s[j + 1:]
	mid = s[i:j + 1]
	new = mid + '#' + mid[::-1]
	x = kmp(new)
	nnew = mid[::-1] + '#' + mid[::-1][::-1]
	y = kmp(nnew)
	if x > y:
		ans = left + new[:x] + right
	else:
		ans = left + nnew[::-1][:y][::-1] + right
	print(ans)


def z_function(s, z):
	n = len(s)
	(l, r, k) = (0, 0, 0)
	for i in range(1, n):
		if i > r:
			(l, r) = (i, i)
			while r < n and s[r - l] == s[r]:
				r += 1
			z[i] = r - l
			r -= 1
		else:
			k = i - l
			if z[k] < r - i + 1:
				z[i] = z[k]
			else:
				l = i
				while r < n and s[r - l] == s[r]:
					r += 1
				z[i] = r - l
				r -= 1
import sys
input = sys.stdin.readline
t = int(input())

def solve(ss, res):
	mx = 0
	z = [0] * len(ss)
	z_function(ss, z)
	ls = len(z)
	for i in range(len(z) - 1, -1, -1):
		if z[i] == ls - i:
			mx = max(mx, z[i])
	for i in range(mx):
		res.append(ss[i])
	nn = len(res)
	for i in range(nn - mx - 1, -1, -1):
		res.append(res[i])
	return ''.join(res)
while t:
	res1 = []
	res2 = []
	s = input().split()[0]
	n = len(s)
	if n == 1:
		print(s)
	else:
		i = 0
		j = n - 1
		while i < j:
			if s[i] == s[j]:
				res1.append(s[i])
				res2.append(s[i])
			else:
				break
			i += 1
			j -= 1
		ss = s[i:j]
		ss = ss + '*' + ss[::-1]
		s1 = solve(ss, res1)
		ss = s[i:j + 1]
		ss = ss[::-1] + '*' + ss
		s2 = solve(ss, res2)
		if len(s1) >= len(s2):
			print(s1)
		else:
			print(s2)
	t -= 1


def manacher(s):
	t = ['#']
	for i in range(len(s)):
		t.append(s[i])
		t.append('#')
	n = len(t)
	r = [0] * n
	i = 0
	j = 0
	while i < n:
		while i - j >= 0 and i + j < n and (t[i - j] == t[i + j]):
			j += 1
		r[i] = j
		k = 1
		while i - k >= 0 and i + k < n and (k + r[i - k] < j):
			r[i + k] = r[i - k]
			k += 1
		i += k
		j -= k
	return r
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	s = input()[:-1]
	n = len(s)
	max_ = 0
	for i in range(n + 1):
		if i >= n - i - 1:
			break
		if s[i] == s[n - i - 1]:
			max_ += 1
		else:
			break
	man = manacher(s)
	ans = 0
	tmp = (0, 0)
	for i in range(max_ * 2 + 1, 2 * n + 1 - max_ * 2):
		l = i - (man[i] - 1)
		r = i + (man[i] - 1)
		l = l // 2
		r = r // 2
		diff = max(0, r - (n - max_), max_ - l)
		if r - diff == n - max_ or l + diff == max_:
			pass
		else:
			continue
		if r - diff - (l + diff) > ans:
			ans = r - diff - (l + diff)
			tmp = (l + diff, r - diff)
	(l, r) = tmp
	print(s[0:max_] + s[l:r] + s[n - max_:n])


def longest_prefix(s):
	kmps = s + '*' + s[::-1]
	lps = [0]
	for i in range(1, len(kmps)):
		prev = lps[i - 1]
		while prev > 0 and kmps[prev] != kmps[i]:
			prev = lps[prev - 1]
		lps.append(prev + 1 if kmps[prev] == kmps[i] else 0)
	return lps[-1]
for _ in range(int(input())):
	ss = input()
	s = 0
	e = len(ss) - 1
	i = 0
	while s < e and ss[s] == ss[e]:
		s += 1
		e -= 1
	if s == e:
		s += 1
	pref = longest_prefix(ss[s:e + 1])
	suff = longest_prefix(ss[s:e + 1][::-1])
	if pref >= suff:
		s += pref
	else:
		e -= suff
	print(ss[:s] + ss[e + 1:])


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7

def pal(x):
	x = x + '#' + x[::-1]
	pref = [0] * (len(x) + 5)
	c = 0
	for i in range(1, len(x)):
		while c != 0 and x[c] != x[i]:
			c = pref[c - 1]
		if x[c] == x[i]:
			c += 1
		pref[i] = c
	return x[:c]
for _ in range(I()):
	s = S()
	p = []
	n = len(s)
	ln = 0
	for i in range(n // 2):
		if s[i] == s[-1 - i]:
			p += (s[i],)
			ln += 1
		else:
			break
	print(*p, sep='', end='')
	if n - ln * 2:
		x = pal(s[ln:n - ln])
		y = pal(s[ln:n - ln][::-1])
		if len(y) > len(x):
			x = y
		print(x, end='')
	print(*p[::-1], sep='')


import sys

def kmp(s):
	s = s + '$' + s[::-1]
	temp = [0 for i in range(len(s))]
	j = 0
	for i in range(1, len(s)):
		while j != 0 and s[i] != s[j]:
			j = temp[j - 1]
		if s[i] == s[j]:
			j += 1
			temp[i] = j
	return s[:temp[-1]]
for _ in range(int(input())):
	s = input()
	if s == s[::-1]:
		print(s)
		continue
	n = len(s)
	(i, j) = (0, n - 1)
	while i <= j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			break
	a = ''
	if i <= j:
		(a, b) = (kmp(s[i:j + 1]), kmp(s[i:j + 1][::-1]))
		if len(a) < len(b):
			a = b
		print(s[:i] + a + s[:i][::-1])
	elif j + 1 == i:
		print(s)
	else:
		print(s[:i])


def callps(s):
	n = len(s)
	lps = []
	for i in range(n):
		lps.append(0)
	i = 1
	l = 0
	while i < n:
		if s[i] == s[l]:
			l += 1
			lps[i] = l
			i += 1
		elif l != 0:
			l = lps[l - 1]
		else:
			lps[i] = 0
			i += 1
	return lps[n - 1]

def fun(s):
	n = len(s)
	if n == 1:
		return s
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			break
	res = s[:i]
	s = s[i:n - i]
	premid = s[:callps(s + '#' + s[::-1])]
	postmid = s[::-1][:callps(s[::-1] + '#' + s)]
	if len(postmid) > len(premid):
		mid = postmid
	else:
		mid = premid
	res = res + mid + res[::-1]
	return res
t = int(input())
while t:
	t -= 1
	s = input()
	print(fun(s))


import sys

def lpre(w):
	kk = len(w)
	ww = w[:]
	w.reverse()
	ww += ['1'] * kk + w
	dp = [0] * (3 * kk + 1)
	dp[0] = -1
	for i in range(3 * kk):
		k = dp[i]
		while k >= 0 and ww[k] != ww[i]:
			k = dp[k]
		dp[i + 1] = k + 1
	return min(kk, dp[-1])
for q in range(int(sys.stdin.readline())):
	w = list(sys.stdin.readline().strip())
	n = len(w)
	st = 0
	for i in range(n // 2):
		if w[i] == w[n - 1 - i]:
			st += 1
		else:
			break
	if st == n // 2:
		sys.stdout.write(''.join(w) + '\n')
		continue
	a = w[st:n - st]
	l1 = lpre(a)
	l2 = lpre(a)
	if l1 > l2:
		ans = w[:st] + a[:l1] + w[n - st:]
	else:
		ans = w[:st] + a[len(a) - l2:] + w[n - st:]
	sys.stdout.write(''.join(ans) + '\n')


from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def menacher(S):
	S = '#' + ''.join([i + '#' for i in S])
	n = len(S)
	P = [0] * n
	c = 0
	r = 0
	for i in range(n):
		mirror = 2 * c - i
		if i < r:
			P[i] = min(r - i, P[mirror])
		a = i + 1 + P[i]
		b = i - 1 - P[i]
		while a < n and b >= 0 and (S[a] == S[b]):
			P[i] += 1
			a += 1
			b -= 1
		if i + P[i] > r:
			c = i
			r = i + P[i]
	return (P[1::2], P[2::2])

def solve():
	s = input()
	(lo, hi) = (0, len(s) - 1)
	pref = 0
	while s[lo] == s[hi]:
		pref += 1
		lo += 1
		hi -= 1
		if lo > hi:
			print(s)
			return
	(P1, P2) = menacher(s[lo:hi + 1])
	longest = 0
	longest_term = (0, 0)
	for (i, l) in enumerate(P1):
		if l <= longest:
			continue
		elif i == (l - 1) // 2 or len(P1) - i - 1 == (l - 1) // 2:
			longest = l
			begin = lo + i - (l - 1) // 2
			longest_term = (begin, begin + l)
	for (i, l) in enumerate(P2):
		if l <= longest:
			continue
		elif i == l // 2 - 1 or len(P2) - i - 1 == l // 2:
			longest = l
			begin = lo + i - l // 2 + 1
			longest_term = (begin, begin + l)
	(l, h) = longest_term
	if pref > 0:
		print(s[:pref] + s[l:h] + s[-pref:])
	else:
		print(s[l:h])
	return
mode = 'T'
if mode == 'T':
	t = ri()
	for i in range(t):
		solve()
else:
	solve()


from sys import stdin, gettrace
if not gettrace():

	def input():
		return next(stdin)[:-1]

def longestPalindromes(s):
	T = '#'.join('^{}$'.format(s))
	n = len(T)
	P = [0] * n
	C = R = 0
	for i in range(1, n - 1):
		P[i] = R > i and min(R - i, P[2 * C - i])
		while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
			P[i] += 1
		if i + P[i] > R:
			(C, R) = (i, i + P[i])
	return P

def main():

	def solve():
		ss = input()
		n = len(ss)
		for i in range(n // 2):
			if ss[i] != ss[n - i - 1]:
				break
		else:
			i = n // 2
		if i * 2 == n:
			print(ss)
			return
		pals = longestPalindromes(ss[i:n - i])
		besta = 0
		bestb = 0
		for (j, p) in enumerate(pals):
			if p == j - 1:
				besta = p
		for (j, p) in enumerate(pals[::-1]):
			if p == j - 1:
				bestb = p
		if bestb > besta:
			print(ss[:i] + ss[n - i - bestb:])
		else:
			print(ss[:i + besta] + ss[n - i:])
	q = int(input())
	for _ in range(q):
		solve()
main()