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[1]$ este primul caracter al şirului, T² al doilea, etc. Şirul are lungime N.

Gigel este interesat de prefixele T1, ..., 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 T de teste. Urmează T 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 cel mai mare prefix diferit de T¹, ..., T[i] care este şi sufix pentru T¹, ..., T[i].

Restricţii

• 1 ≤ n ≤ 131072
• 1 ≤ T ≤ 128

Exemplu

Explicaţie

Pentru T¹...T⁵, prefixul T¹,T² este egal cu sufixul T⁴,⁵.

Cum se trimit solutii?