Fişierul intrare/ieşire:	prefixe.in, prefixe.out	Sursă	ONIS 2014, Runda Finala
Autor	Stefan Ciobaca	Adăugată de	FMI No Stress •fmins123
Timp execuţie pe test	1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Prefixe

După cum ştiţi, lui Gigel îi plac cifrele 0 şi 1. În această problemă, îi place şi cifra 2. El analizează un şir de caractere T format doar din 0, 1 şi 2 şi este fascinat de şabloanele pe care le observă în şir. Caracterul T₁ este primul caracter al şirului, T₂ al doilea, etc. Şirul are lungime N.

Gigel este interesat de prefixele T₁, ..., T_i ale acestui şir (1 ≤ i ≤ N). El observă că un astfel de prefix de lungime i are la rândul lui anume prefixe care îi sunt şi sufixe. De exemplu, dacă T = 0101012 şi i = 5, în prefixul 01010 se găseşte prefixul 010 care este şi sufix. Vă roagă să gasiţi pentru fiecare prefix T₁, ..., T_i lungimea celui mai mare prefix diferit de T₁, ..., T_i care este şi sufix al T₁, ..., T_i.

Date de intrare

Fişierul de intrare prefixe.in conţine pe prima linie numărul Z de teste. Urmează Z linii, fiecare cu câte un test. Un test constă dintr-un şir format din 0, 1 şi 2.

Date de ieşire

În fişierul de ieşire prefixe.out afişaţi pentru fiecare prefix T₁, ..., T_i al şirului dat la intrare lungimea celui mai mare prefix diferit de T₁, ..., T_i care este şi sufix pentru T₁, ..., T_i. Lungimile trebuie separate prin spaţii.

Restricţii

• 1 ≤ N ≤ 131072
• 1 ≤ Z ≤ 128

Exemplu

Explicaţie

Pentru T₁...T₅, prefixul T₁,T₂ este egal cu sufixul T₄,₅, deci al 5-lea număr de la ieşire este 2, lungimea şirului T₁,T₂.

Cum se trimit solutii?