Dada una cadena de caracteres \(s\), de longitud \(n\), tu tarea consiste en encontrar la subcadena palindrómica más larga.
Un palíndromo es una palabra o frase que se lee igual de izquierda a derecha que de derecha a izquierda. Por ejemplo, las palabras "reconocer", "ala" o "anilina" son palíndromos.
Para el reconocimiento de los palíndromos no distinguiremos entre mayúsculas y minúsculas. Además, ignoraremos los espacios (los espacios no cuentan al verificar si es palíndromo). Además, los espacios no cuentan para determinar la longitud del palíndromo más largo, y al momento de imprimirlo, se deberá prescindir de los posibles espacios innecesarios al principio y final de la subcadena.
Por ejemplo, "AB c CBA" es un palíndromo válido porque, al ignorar espacios y mayúsculas/minúsculas, se convierte en "abccba".
Si existen varias subcadenas palindrómicas de longitud máxima, deberás imprimir aquella que sea lexicográficamente menor (considerando el formato original de la subcadena).
Entrada
La primera línea contiene un entero \(t\) (\(1 \le t \le 100\)), representando el número de casos de prueba.
Cada caso de prueba está compuesto por una sola línea, la cadena de caracteres \(s\), de longitud \(n\) (\(1 \le n \le 1000\)).