#P3231. [HNOI2013] 消毒

[HNOI2013] 消毒

题目描述

最近在生物实验室工作的小 T 遇到了大麻烦。 由于实验室最近升级的缘故,他的分格实验皿是一个长方体,其尺寸为 a×b×ca\times b\times c。为了实验的方便,它被划分为 a×b×ca\times b\times c 个单位立方体区域,每个单位立方体尺寸为 1×1×11\times 1\times 1,并用 (i,j,k)(i,j,k) 标识一个单位立方体。这个实验皿已经很久没有人用了。现在,小 T 被导师要求将其中一些单位立方体区域进行消毒操作(每个区域可以被重复消毒)。

而由于严格的实验要求,他被要求使用一种特定的 F 试剂来进行消毒。 这种 F 试剂特别奇怪,每次对尺寸为 x×y×zx\times y\times z 的长方体区域(它由 x×y×zx\times y\times z 个单位立方体组成)进行消毒时,只需要使用 min(x,y,z)\min(x,y,z) 单位的 F 试剂。F 试剂的价格不菲,这可难倒了小 T。

现在请你告诉他,最少要用多少单位的 F 试剂。

输入格式

本题有多组数据。

第一行是一个正整数 DD,表示数据组数。

接下来是 DD 组数据,每组数据第一行是三个正整数 a,b,ca,b,c 表示实验皿的尺寸。

接下来会出现 aabbcc 列的用空格隔开的 01 矩阵,0 表示对应的单位立方体不要求消毒,1 表示对应的单位立方体需要消毒:如,如果第 1101 矩阵的第 22 行第 33 列为 1,则表示单位立方体 (1,2,3)(1,2,3) 需要被消毒。

输出格式

DD 行,每行一个整数,表示对应实验皿最少要用多少单位的 F 试剂。

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

提示

样例 1 解释

对于区域 (1,1,3)(2,2,4)(1,1,3)-(2,2,4)(1,1,1)(4,4,1)(1,1,1)-(4,4,1) 消毒,分别花费 22 个单位和 11 个单位的 F 试剂。

数据规模与约定

对于 100%100\% 的数据,保证 1a,b,c5×1031\le a,b,c\le 5\times 10^3abc5×103abc\le 5\times 10^3,且 1D31\le D\le 3