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$.

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

h2. Date de intrare