logo AlgoBeat OnlineJudge
登录 注册

#103140. [BZOJ 3140] [Hnoi2013]消毒

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

最近在生物实验室工作的小 T 遇到了大麻烦。由于实验室最近升级的缘故,他的分格实验皿是一个长方体,其尺寸为 。为了实验的方便,它被划分为 个单位立方体区域,每个单位立方体尺寸为 ,并用 标识一个单位立方体。这个实验皿已经很久没有人用了。现在,小 T 被导师要求将其中一些单位立方体区域进行消毒操作(每个区域可以被重复消毒)。而由于严格的实验要求,他被要求使用一种特定的 F 试剂来进行消毒。这种 F 试剂特别奇怪,每次对尺寸为 的长方体区域(它由 个单位立方体组成)进行消毒时,只需要使用 单位的 F 试剂。F 试剂的价格不菲,这可难倒了小 T。现在请你告诉他,最少要用多少单位的 F 试剂。

输入格式

**本题有多组数据。**第一行是一个正整数 ,表示数据组数。接下来是 组数据,每组数据第一行是三个正整数 表示实验皿的尺寸。接下来会出现 列的用空格隔开的 01 矩阵,0 表示对应的单位立方体不要求消毒,1 表示对应的单位立方体需要消毒:如,如果第 01 矩阵的第 行第 列为 1,则表示单位立方体 需要被消毒。

输出格式

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

样例

样例输入 #1

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

样例输出 #1

3

样例说明

对于区域 消毒,分别花费 个单位和 个单位的 F 试剂。

数据范围与提示

对于 的数据,保证 ,且