题目描述

Arsh 最近发现了一块旧的矩形电路板，想要回收利用。该电路板有 $R$ 行 $C$ 列方格。

电路板的每个方格都有一个厚度（单位为毫米）。第 $r$ 行第 $c$ 列的方格厚度为 $V_{r,c}$。如果每一行中，最厚方格与最薄方格的厚度差不超过 $K$，则称该电路板是 好的。

由于原始电路板可能不是好的，Arsh 想从中找出一个好的子电路板。子电路板可以通过从原始板中选取一个与坐标轴对齐的子矩形，并取该子矩形内的所有方格得到。Arsh 希望你能帮助他找出原始板中最大的好子矩形所含的方格数。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $R$、$C$ 和 $K$，分别表示行数、列数以及每行允许的最大厚度差。

随后 $R$ 行，每行包含 $C$ 个整数。第 $r$ 行的第 $c$ 个整数为 $V_{r,\, c}$，表示第 $r$ 行第 $c$ 列方格的厚度。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一个好的子矩形中所包含的最大方格数。

3
1 4 0
3 1 3 3
2 3 0
4 4 5
7 6 6
4 5 0
2 2 4 4 20
8 3 3 3 12
6 6 3 3 3
1 6 8 6 4

Case #1: 2
Case #2: 2
Case #3: 6

3
1 4 2
3 1 3 3
3 3 2
0 5 0
8 12 3
7 10 1
4 4 8
20 10 20 10
10 4 5 20
20 5 4 10
10 20 10 20

Case #1: 4
Case #2: 3
Case #3: 4

提示

额外样例 – 测试集 2

以下样例说明了各测试用例的情况。对于每个测试用例，包含最多方格的好子电路板用绿色高亮显示。

:::align{center} :::

限制条件

$1 \le T \le 50$。

$1 \le R \le 300$。

$1 \le C \le 300$。

对于所有 $i, j$，$0 \le V_{i,\,j} \le 10^3$。

测试集 1（可见）

$K = 0$。

测试集 2（隐藏）

$0 \le K \le 10^3$。

翻译由 DeepSeek V4 Pro 完成