Un palíndrome es una cadena que se lee igual de izquierda a derecha como lo hace desde la derecha. Por ejemplo, I, GAG y MADAM son palíndromos, pero ADAM no lo es. En este sentido, consideramos también la cadena vacía como un palíndrome.

De cualquier cadena no palindrómica, siempre se puede quitar algunas letras, y obtener una subsecuencia palindrómica. Por ejemplo, dada la cadena de ADAM, se elimina la letra M y obtener un palíndrome ADA.

Escriba un programa para determinar el palíndrome de mayor longitud que se puede obtener a partir de una cadena.

La primera línea de entrada contiene un número entero ($T \leq 60$). Cada una de las siguientes $T$ líneas  es una cadena, cuya longitud es siempre menor que $1000$.

Para el $90 \%$ de los casos de prueba, cadena de longitud menor o igual que 255.

Para cada cadena de entrada, el programa debe imprimir la longitud del mayor palíndrome se puede obtener mediante la eliminación de cero o más caracteres de la misma.