Eşti în continuare la laboratorul de algoritmi. Laborantul şi-a mai revenit. Îşi dă jos ochelarii de soare şi spune:

Spunem că un şir de caractere $A$ este o $K-repetiţie$ dacă există un şir de caractere $B$ astfel încât $A = B + B + B + .. (de K ori în total)$, unde $+$ denotă operaţia de concatenare. Spre exemplu, "dada" este o $2-repetitie$, iar $andeandeande$ este o $3-repetitie$.

Spunem că un şir de caractere $A$ este o $K-repetiţie$ dacă există un şir de caractere $B$ astfel încât $A = B + B + B + .. (de K ori în total)$, unde $+$ denotă operaţia de concatenare. Spre exemplu, "dada" este o $2-repetitie$, iar $andreiandreiandrei$ este o $3-repetitie$.

Având un şir de caractere $S$, trebuie să aflaţi câte subsecvenţe de ale sale sunt $K-repetiţii$, pentru toţi $K$ de la $1$ la $N$.
h2. Date de intrare

Fişierul de intrare $boring.in$ ...

Fişierul de intrare $boring.in$ va contine pe prima sa linie valoarea $T$, reprezentand numarul de teste din fisier. Urmatoarele $T$ linii

h2. Date de ieşire