F - Sufijos b-semejantes

Time limit: 7 seconds
Memory limit: 256 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

Fito está estudiando las relaciones entre dos palabras y encuentra un concepto interesante. Se dice que dos palabras son $b$-semejantes si ambas tienen un prefijo común de longitud mayor o igual que $b$. Este concepto se puede usar para agrupar palabras que se derivan de la misma raíz.


Fito quiere ahora aplicar esta relación, pero entre la palabra y sus sufijos. Queremos saber para un texto $S$ cuantos sufijos son $b$-semejantes con él para distintos valores de $b$.

Input

La primera línea de la entrada es un entero $T (1 \leq T \leq 10)$ que indica la cantidad de casos de pruebas. La primera línea de cada caso de prueba contiene el texto $S(1 \leq |S| \leq 10^5)$. El texto S está formado por letras minúsculas del alfabeto latino. La siguiente línea es un entero $M (1 \leq M \leq 10^5)$ que representa la cantidad de valores de $b$. Después le sigue una línea con $M$ valores separados por un espacio, cada uno es un valor de $b (0 \leq b \leq 10^5)$.

Output

Por cada valor de $b$ se debe responder cuantos sufijos de $S$ son b-semejantes con él. Todas las respuestas de un caso de prueba deben aparecer en una línea separadas por un espacio.

Sample test(s)

Input
1 abcaba 2 1 2
Output
3 2