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

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.

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.

h2. Date de intrare

Fişierul de intrare $harddp.in$ va contine pe prima linie un numar natural $T$ , reprezentand numarul de teste.A doua linie contine $N$,numar intreg.A treia linie contine un sir binar de caractere de lungime $N$ ( fara spatii intre caractere ). Structura testului se repeta de $T$ ori.

Fişierul de intrare $harddp.in$ va contine pe prima linie un numar natural $T$, reprezentand numarul de teste. A doua linie contine $N$, numar intreg. A treia linie contine un sir binar de caractere de lungime $N$ (fara spatii intre caractere). Structura testului se repeta de $T$ ori.

h2. Date de ieşire

În fişierul de ieşire $harddp.out$ vor fi $T$ linii,cate una pentru fiecare dintre teste.O linie contine un sir de caracte binar de lungime $N$.

În fişierul de ieşire $harddp.out$ vor fi $T$ linii, cate una pentru fiecare test. O linie contine un sir de caractere binar de lungime $N$.

h2. Restricţii

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

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

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

table(example). |_. harddp.in |_. harddp.out |
|1
3

010
|
101

100
|011

|

h3. Explicaţie
 
...
 

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