== include(page="template/taskheader" task_id="perioada") ==

Mona si Lisa sunt impatimite ale jocurilor de noroc. In fiecare seara ele isi incearca sansa la o ruleta electronica speciala, care afiseaza la fiecare tura cate o litera mica a alfabetului englez. Cele doua fete au jucat noaptea trecuta $N$ ture, pariind pe exact o litera in fiecare tura. Deoarece au pierdut o suma foarte mare de bani (in dolari), fetele se gandesc ca ruleta trebuie sa fie masluita si doresc sa demonstreze stiintific acest lucru. Ele au notat pe o foaie $N$ caractere, al $i$-lea caracter reprezentand litera afisata de ruleta la cea de a $i$-a tura. Mona observa ca unele secvente de caractere aflate pe pozitii consecutive sunt periodice, adica sunt formate prin concatenarea de cel putin *doua* ori a aceluiasi sir. De exemplu, sirurile $abcabc$ si $ananan$ sunt periodice, dar $abac$ nu este. Lisa realizeaza ca ruleta este masluita daca aceasta a generat multe secvente periodice. Lisa alege astfel $M$ secvente pentru care doreste sa determine daca sunt sau nu periodice. In cazul in care o secventa e periodica Lisa vrea sa stie in cate moduri poate fi obtinuta prin concatenarea aceluiasi sir.

Mona si Lisa sunt impatimite ale jocurilor de noroc. In fiecare seara ele isi incearca sansa la o ruleta electronica speciala, care afiseaza la fiecare tura cate o litera mica a alfabetului englez. Cele doua fete au jucat noaptea trecuta $N$ ture, pariind pe exact o litera in fiecare tura. Deoarece au pierdut o suma foarte mare de bani (in dolari), fetele se gandesc ca ruleta trebuie sa fie masluita si doresc sa demonstreze stiintific acest lucru. Ele au notat pe o foaie $N$ caractere, al $i$-lea caracter reprezentand litera afisata de ruleta la cea de a $i$-a tura. Mona observa ca unele secvente de caractere aflate pe pozitii consecutive sunt periodice, adica sunt formate prin concatenarea de cel putin *doua* ori a aceluiasi sir. De exemplu, sirurile $abcabc$ si $ananan$ sunt periodice, dar $abac$ nu este. Lisa realizeaza ca ruleta este masluita daca aceasta a generat multe secvente periodice. Lisa alege astfel $M$ secvente pentru care doreste sa determine daca sunt sau nu periodice.

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $perioada.out$ vor fi afisate M numere intregi, valoarea de pe linia $i$ reprezentand numarul de moduri in care poate fi considerata concatenare cea de a $i$-a secventa din fisierul de intrare.

În fişierul de ieşire $perioada.out$ vor fi afisate M cifre binare, cifra de pe linia $i$ fiind $1$ doar daca cea de a $i$-a secventa din fisierul de intrare este periodica.

h2. Restricţii