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

Sorin a citit de curand “Legendele Olimpului”, carte ce i-a deschis calea catre un maret destin. Asemeni lui Orfeu in cautarea lui Euridice, acesta porneste in calatoria sa initiatica cunoscuta drept “mitul coborarii in beci”. Calea sa il poarta pe urmele algoritmului celui mai lung subsir comun. Usa grea din lemn se inchide in spatele sau.
 
Comisia lumii subterane ii da un sir A de N caractere de 0 si 1. El trebuie sa gaseasca un sir B, de lungime N , format tot din 0 si 1, astfel incat lungimea celui mai lung subsir comun dintre A si B sa fie minima. Ajuta-l pe Sorin sa transceada catre stadiul olimpic prin rezolvarea problemei.

Sorin a invatat recent algoritmul celui mai lung subsir comun dintre 2 siruri. Acum, stand in fata legendarului beci el se gandeste la urmatoarea problema.
Se da un sir A din $N$ caractere de 0 si 1. El trebuie sa gaseasca un sir B, de lungime $N$ , format tot din 0 si 1, astfel incat lungimea celui mai lung subsir comun dintre A si B sa fie minima.

h2. Date de intrare

h2. Restricţii

* $1 ≤ T ≤ 75$
* $1 ≤ N ≤ 1000$

* $... ≤ ... ≤ ...$

* Va rugam sa nu spuneti comisiei ce ar spune Sorin!
h2. Exemplu