Tienes un montón de letras (dado como un texto \(s\)). ¿Cuál es el largo del palíndromo más largo que puedes formar usando algunas de esas letras, cada una a lo más una vez? Las mayúsculas y las minúsculas son letras distintas: Aa no es un palíndromo.

Entrada

La primera línea tiene \(T\) y siguen \(T\) líneas con un texto \(s\) cada una, de letras inglesas mayúsculas y minúsculas. La suma de los largos es a lo más \(2 \cdot 10^5\).

Salida

Para cada texto, el largo del palíndromo más largo.

Ejemplo 1

Entrada

3
abccccdd
a
Aa

Salida

7
1
1

Ejemplo 2

Entrada

1
bananas

Salida

5

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