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.

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