Să considerăm un cub de latură N, compus din NxNxN celule. O celulă (i,j,k) (0≤i,j,k≤N-1) conţine o valoare C(i,j,k) care poate fi ori 0, ori 1. Dorim să amplasăm în interiorul cubului două paralelipipede, astfel încât fiecare celulă (i,j,k) cu C(i,j,k)=1 să se afle în interiorul cel puţin unui paralelipiped. Cele două paralelipipede se pot intersecta.
Un paralelipiped este definit de 3 intervale [a1,b1], [a2,b2], [a3,b3] şi conţine în interiorul său toate celulele (i,j,k) cu a1≤i≤b1, a2≤j≤b2 şi a3≤k≤b3.
Volumul paralelipipedului este (b1-a1+1)•(b2-a2+1)•(b3-a3+1).
Cerinţă
Determinaţi o amplasare a două paralelipipede care să respecte condiţiile specificate, astfel încât suma volumelor celor două paralelipipede să fie minimă.
Date de intrare
Prima linie a fişierului de intrare ppcover.in conţine numărul T de teste descrise în continuare. Prima linie a fiecărui test conţine numărul N, reprezentând dimensiunea laturii cubului. Următoarele N2 linii conţin câte N caractere fiecare (plus caracterul de linie nouă la sfârşitul fiecărei linii).
A L-a astfel de linie (1≤L≤N2) corespunde celulelor (i,j,k) pentru care i=(L-1) div N şi j=(L-1) mod N. Al k-lea caracter (1≤k≤N) de pe a L-a linie dintre cele N2 corespunde valorii C(i,j,k-1); dacă caracterul este ‘0’ atunci C(i,j,k-1)=0 şi dacă caracterul este ‘1’ atunci C(i,j,k-1)=1.
Date de ieşire
În fişierul de ieşire ppcover.out veţi afişa câte o linie pentru fiecare test dat în fişierul de intrare, conţinând suma minimă a volumelor celor două paralelipipede.
Restricţii
1 ≤ T ≤ 40
1 ≤ N ≤ 40
Este permis ca paralelipipedele (unul dintre ele sau ambele) să aibă volumul 0.