Un día Alice visitó el centro comercial Plaza del sol para comprar joyas para su próximo aniversario de bodas. En PLaza del Sol, todas las tiendas de joyería tiene sus propios métodos de descuentos para atraer a los clientes. Sin embargo solo un método de descuento llamó la atención de Alice.

Alice consulto el descuento y le explicaron los siguiente. Si Alice compra una unidad de joya, ella puede conseguir una unidad de joya adicional con el mismo color y sin cargo en le total a pagar. Sin duda es una oferta muy dificl de rechazar.

A continuación y sin pensarlo dos veces Alice escribe las joyas que necesita en una cadena S, cada letra en la cadena denota una joya, las mismas letras denotan los mismos colores de joyas, y las letras diferentes denotan los diferentes colores de otras joyas. El costo de cada joya es 1. Su tarea consiste en calcular el costo mínimo para conseguir todas las joyas de Alice.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 ≤ M ≤ 100)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

S : La cadena que contien las joyas que Alice necesita. La cadena S se distingue entre mayúsculas y minúsculas, y contiene sólo caracteres del alfabeto inlges en el rango [az], [AZ]. (1 ≤ |S| ≤ 10000, donde |S| representa la longitud de la cadena S)

Output

Salida. El costo mínimo de la compra de joyas para cada caso de prueba.

Entrada de ejemplo