Para cada texto, encuentra su subcadena (tramo contiguo) más larga que sea un palíndromo. Si hay varias del mismo largo, imprime la que empieza más a la izquierda.

Entrada

La primera línea tiene \(T\) y siguen \(T\) líneas con un texto cada una, de entre \(1\) y \(1000\) letras minúsculas y dígitos. La suma de los largos es a lo más \(3000\).

Salida

Para cada texto, la subcadena palíndroma más larga.

Ejemplo 1

Entrada

2
babad
cbbd

Salida

bab
bb

Ejemplo 2

Entrada

1
a

Salida

a

Basado en el problema 5 de LeetCode, Longest Palindromic Substring, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.