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

* $1 ≤ T ≤ 1000$
* $1 ≤ |S| ≤ 300.000$
* Suma valorilor lui $|S|$ în cadrul aceluiaşi fişier de intrare este cel mult egală cu $300.000$.

* $S$ contine doar litere mici ale alfabetului englez.

* O subsecvenţă a unui şir este un subşir de elemente *consecutive* ale acestuia.
h2. Exemplu
table(example). |_. boring.in |_. boring.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
aaaaa
barbaraa
| 15 6 3 2 1
36 2 0 0 0 0 0 0

|
h3. Explicaţie

...

Notaţi că, în general, toate subsecvenţele lui $S$ sunt $1-repetiţii$.

== include(page="template/taskfooter" task_id="boring") ==