ppcover

Cerință

Să considerăm un cub de latură $N$, compus din $N \times N \times N$ celule. O celulă $(i,j,k)$, $(0 \leq i,j,k \leq 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 $[a_1,b_1]$, $[a_2,b_2]$, $[a_3,b_3]$ şi conţine în interiorul său toate celulele $(i,j,k)$ cu $a_1 \leq i \leq b_1$, $a_2 \leq j \leq b_2$ şi $a_3 \leq k \leq b_3$.

Volumul paralelipipedului este $(b_1-a_1+1) \cdot (b_2-a_2+1) \cdot (b_3-a_3+1)$

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 $N^2$ 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 \leq L \leq N^2)$ corespunde celulelor $(i,j,k)$ pentru care $i=(L-1)$ div $N$ şi $j=(L-1)$ mod $N$. Al $k$-lea caracter $(1 \leq k \leq N)$ de pe a $L$-a linie dintre cele $N^2$ 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 și precizări

• $1 \leq T \leq 40$
• $1 \leq N \leq 40$
• Este permis ca paralelipipedele (unul dintre ele sau ambele) să aibă volumul $0$.

Exemplu

ppcover.in

2
2
11
00
10
01
3
001
100
101
011
000
000
000
011
100

ppcover.out

5
22