Acabes d'arribar a casa després de classe i damunt de la taula veus un quadern per a acolorir que li ha comprat la teva mare al teu germà petit de 8 anys. Per curiositat l'obres per a donar-li un cop d'ull, a l'instant t'adones que el teu germà ja l'ha utilitzat, després de cinc segons veient el mal que acoloreix el teu germà t'has adonat de les següents coses:

1 - El dibuix tracta del cap d'un lleó en un quadrat d'una quadrícula, al qual, li has d'acolorir la cabellera.

2 - Per a acolorir la cabellera del lleó necessites seguir les següents normes:

    1 - La cabellera ha de ser quadrada.

    2 - La cabellera no pot sortir de la quadrícula.

A l'estona d'haver arribat casa arriba la teva mare amb el teu germà i ell et demana ajuda per a poder acolorir al lleó.

Tu, com un entusiasmat estudiant al qual li encanta la programació, decideixes fer un programa per a ajudar el teu germà a acolorir el dibuix.

Per a fer el repte més difícil treballaràs sobre el que ha acolorit el teu germà i a més afegeixes algunes regles a les quals ja et dona el quadern, les regles són les següents:

    1 - Et fixaràs als voltants de la cara del lleó, quanta cabellera hi ha acolorida.

    2 - Si hi ha més del 50% de l'àrea acolorida, emplenaràs l'àrea buida.

    3 - Si la condició anterior no es compleix, esborraràs tota la cabellera des de la vora per a fora.

    4 - Si has emplenat l'àrea, tornaràs a mirar al voltant però amb una àrea més gran.

Entrada

L’entrada comença amb un valor enter que indicarà el número de casos de prova. Per cada cas de prova, rebràs:

• un número (N) que serà el nombre de files / columnes de la matriu

• N*N enters amb valor 0,1,2

    (2) serà la cara del lleó, (1) són els trossos de cabellera que ha acolorit el teu germà, (0) és l’espai buit.

  (solament hi ha un valor 2 en tota la matriu)

Sortida

Per cada cas de prova s’imprimirà el dibuix finalitzat a mes de les següents tres característiques: Melena Pintada: Nº Melena Esborrada: Nº Gruix Melena: Nº

Exemple d'Entrada

3
3
1 2 1
0 0 0
1 1 1
4
0 0 1 1
0 2 0 1
1 1 1 1 
1 1 1 1
5
0 0 1 1 1
0 0 0 1 1
0 2 1 1 1 
1 1 1 0 1
1 0 1 1 1

Exemple de Sortida

0 2 0 
0 0 0 
0 0 0 
Melena Pintada: 0
Melena Esborrada: 5
Gruix de la Melena: 0
1 1 1 0 
1 2 1 0 
1 1 1 0 
0 0 0 0 
Melena Pintada: 4
Melena Esborrada: 7
Gruix de la Melena: 1
0 0 0 0 0 
1 1 1 0 0 
1 2 1 0 0 
1 1 1 0 0 
0 0 0 0 0 
Melena Pintada: 4
Melena Esborrada: 12
Gruix de la Melena: 1