Description

Xiao T has run into big trouble while working in a biology lab. Due to a recent upgrade, his compartmentalized dish is a rectangular box with dimensions $a\times b\times c$. For convenience, it is partitioned into $a\times b\times c$ unit cubes, each of size $1\times 1\times 1$, and a unit cube is denoted by $(i, j, k)$. The dish has not been used for a long time. Now, Xiao T is required by his advisor to disinfect some of the unit cubes (each unit cube may be disinfected multiple times).

Due to strict experimental requirements, he must use a specific reagent F. This reagent F is peculiar: each time he disinfects a rectangular box of size $x\times y\times z$ (consisting of $x\times y\times z$ unit cubes), it costs only $\min(x, y, z)$ units of reagent F. Since reagent F is expensive, Xiao T wants to minimize the total amount used.

Please tell him the minimum total units of reagent F required.

Input Format

This problem contains multiple testcases.

• The first line contains a positive integer $D$, the number of testcases.
• For each testcase, the first line contains three positive integers $a, b, c$, the dimensions of the dish.
• Then follow $a$ blocks. For each $i=1,2,\dots,a$, read a $b$-row, $c$-column 01 matrix with entries separated by spaces. 0 means the corresponding unit cube does not need disinfection, and 1 means it needs disinfection. For example, if the $(2, 3)$ entry of the first 01 matrix is 1, then unit cube $(1, 2, 3)$ must be disinfected.

Output Format

Output $D$ lines. For each testcase, output one integer: the minimum total units of reagent F required.

1
4  4 4
1  0 1 1
0  0 1 1
0  0 0 0
0  0 0 0
0  0 1 1
1  0 1 1
0  0 0 0
0  0 0 0
0  0 0 0
0  0 0 0
1  0 0 0
0  0 0 0
0  0 0 0
0  0 0 0
0  0 0 0
1  0 0 0

3

Hint

Sample 1 explanation: Disinfecting regions $(1,1,3)-(2,2,4)$ and $(1,1,1)-(4,4,1)$ costs $2$ units and $1$ unit of reagent F, respectively.

Constraints: For $100\%$ of the testdata, it is guaranteed that $1\le a,b,c\le 5\times 10^3$, $abc\le 5\times 10^3$, and $1\le D\le 3$.

Translated by ChatGPT 5