Una partición de una cadena s es un conjunto de uno o mas subcadenas no vacÍas y que no se solapan (la nombramos como ~a_1, a_2, a_3,...,a_d~), tal que s es su concatenación: ~s = a_1 + a_2 + a_3 + ... + a_d~. Llamarenos a estas subcadenas “pedazos” y definimos como longitud ~d~ de la particion al numero de “pedazos”.

Podemos representar la partición de una cadena encribiendo cada pedazo entre paréntesis. Por ejemplo, la cadena “decode” puede ser particionada como: (d)(ec)(ode) or (d)(e)(c)(od)(e) o (decod)(e) o (decode) o (de)(code)

Una partición es palindrome si sus “pedazos” forman un palindrome cuando consideramos cada pedazo como una unidad atómica. Por ejemplo, las particiones palindrome de "decode" son: (de)(co)(de) y (decode) . Esto tambien ilustra que cada palabra tiene una partición palindrome trivial de longitud 1.

Tu tarea es calcular el número máximo posible de “pedazos” en una partición palindrome.

Entrada

La entrada comienza con el número de casos de prueba ~t (1 \le t \le 10)~ en la primera línea. Las siguientes ~t~ líneas describen los casos de pruebas individuales consistentes de una palabra simple ~s (1 \le n \le10^6)~, conteniendo solamente letras minúsculas del alfabeto inglés. No hay espacios en la entrada.

Salida

Para cada caso de prueba escribir un número simple: la longitud de la partición palindrome más larga de la palabra ~s~ entrada.

Ejemplo de Entrada

4
bonobo
deleted
racecar
racecars

Ejemplo de Salida

3
5
7
1

Subtareas

Subtarea 1 (15 puntos) ~n \le 30~

Subtarea 2 (20 puntos) ~n \le 300~

Subtarea 3 (25 puntos) ~n \le 10 000~

Subtarea 4 (40 puntos) sin restricciones adicionales.