Fişierul intrare/ieşire:	bitmap.in, bitmap.out	Sursă	Happy Coding 2007
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.275 sec	Limită de memorie	67583 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Bitmap

Niste cercetatori au inventat un mod de a codifica un bitmap de dimensiuni MxN sub forma unui sir de caractere. Sirul este, de fapt, o reprezentare a unor operatii efectuate asupra bitmap-ului. Algoritmul de codificare este descris in continuare:

• daca toate celulele bitmap-ului au culoarea 1, atunci codificarea este "1"
• daca toate celulele bitmap-ului au culoarea 0, atunci codificarea este "0"
• altfel, trebuie sa alegeti una din urmatoarele modalitati pentru a codifica bitmap-ul:
  • Codificare(B) = "A" + Codificare(B₁) + Codificare(B₂), unde "+" reprezinta operatia de concatenare, B₁ este bitmap-ul rezultat prin pastrarea primelor M/2 linii ale bitmap-ului B si a tuturor coloanelor, iar B₂ este bitmap-ul rezultat prin pastrarea ultimelor M-M/2 linii ale bitmap-ului B si a tuturor coloanelor (astfel, B₁ va avea M/2 linii si N coloane, iar B₂ va avea M-M/2 linii si N coloane).
  • Codificare(B) = "B" + Codificare(B₁) + Codificare(B₂), unde "+" reprezinta operatia de concatenare, B₁ este bitmap-ul rezultat prin pastrarea primelor N/2 coloane ale bitmap-ului B si a tuturor liniilor, iar B₂ este bitmap-ul rezultat prin pastrarea ultimelor N-N/2 linii ale bitmap-ului B si a tuturor liniilor (astfel, B₁ va avea M linii si N/2 coloane, iar B₂ va avea M linii si N-N/2 coloane).
  • Codificare(B) = "C" + Codificare(B₁) + Codificare(B₂), unde "+" reprezinta operatia de concatenare, B₁ este bitmap-ul rezultat prin pastrarea tuturor liniilor cu numere impare ale bitmap-ului B (liniile sunt numerotate incepand de la 1) si a tuturor coloanelor, iar B₂ este bitmap-ul rezultat prin pastrarea tuturor liniilor cu numere pare ale bitmap-ului B si a tuturor coloanelor (astfel, B₁ va avea M-M/2 linii si N coloane, iar B₂ va avea M/2 linii si N coloane).
  • Codificare(B) = "D" + Codificare(B₁) + Codificare(B₂), unde "+" reprezinta operatia de concatenare, B₁ este bitmap-ul rezultat prin pastrarea tuturor coloanelor cu numere impare ale bitmap-ului B (coloanele sunt numerotate incepand de la 1) si a tuturor liniilor, iar B₂ este bitmap-ul rezultat prin pastrarea tuturor coloanelor cu numere pare ale bitmap-ului B si a tuturor liniilor (astfel, B₁ va avea M linii si N-N/2 coloane, iar B₂ va avea M linii si N/2 coloane).

Fiind dat un bitmap, gasiti lungimea celei mai scurte codificari a acestuia.

Date de intrare

Prima linie a fisierului de intrare bitmap.in contine numarul de teste T. Urmatoarele linii descriu cele T teste. Prima linie a fiecarui test contine 2 numere intregi M si N, reprezentand numarul de linii si de coloane ale bitmap-ului. Fiecare din rumatoarele M linii contine un sir de N caractere din multimea {'0','1'}, reprezentand cate o linie a bitmap-ului.

Date de iesire

Pentru fiecare test, afisati in fisierul de iesire bitmap.out cate o linie continand lungimea minima a unei codificari a bitmap-ului din testul respectiv.

Restrictii

• 1 ≤ T ≤ 1105
• 1 ≤ M,N ≤ 11

Exemplu

Explicatie

O codificare de lungime minima pentru primul test este: C01
O codificare de lungime minima pentru cel de-al doilea test este: BD01A1D10

Cum se trimit solutii?