Programacion Competitiva Bolivia

El área de procesamiento de texto es una parte muy importante en las ciencias de la computación.
Por ejemplo, en la búsqueda de cierta cadena en un texto que puede llegar a ser muy extenso.
Knuth, Morris y Pratt desarrollaron un algoritmo que nos permite hacer esta búsqueda con
una complejidad menor a la búsqueda por fuerza bruta.

Para llevar a cabo el algoritmo KMP (en honor a sus respectivas iniciales), previamente se
necesita pre-procesar el texto base.

Dicho preprocesamiento consiste en que por cada posición i, se calcula cual sería el prefíjo más
largo que tambien es un prefíjo del texto conformado desde su primera letra hasta esa posición
i.

Como restricción, dichos sufíjos/prefíjos, deben ser de longitud menor a la sub-cadena actual.
La defínición simple de un suíjo, es aquella sub-cadena contínua que termina en el extremo
fínal de un texto.

Por ejemplo, la palabra `zombie', tiene como sufíjos a:

e
ie
bie
mbie
ombie
zombie

La defínición simple de un prefíjo, lo inverso a sufíjo, es aquella sub-cadena que contiene el
inicio de un texto.

Por ejemplo, la palabra `zombie', tiene como prefíjos a:

z
zo
zom
zomb
zombi
zombie

Volviendo al algoritmo KMP, si el texto base fuera:

12345678901
abracadabra

Para la posición i = 11, el sufíjo más largo que tambien es prefíjo es la cadena 'abra' de longitud 4.

Si para cierta posición no existiera un prefíjo/sufíjo que cumpla las condiciones debidas, la
respuesta para esa posición es cero.

Entrada

La entrada comienza con un núumero NC, el número de casos de prueba.

A continuación, existen NC casos de prueba, cada cual consiste en:
Una cadena conformada únicamente por números y letras del alfabeto inglés.

Cada cadena no excederá los 200 caracteres.

Salida

Por cada caso de prueba, imprimir el número de caso de prueba y por cada posición i, imprimir
el indice i y la respuesta respectiva a dicha posición i.

Si la respuesta para un índice i es 0, dicho resultado no deberá ser presentado en la salida.

Ejemplos de entrada

1
abracadabra

Ejemplos de salida

Caso 1:
4: 1
6: 1
8: 1
9: 2
10: 3
11: 4