题目描述

Codejammon 的训练师们正在积极寻找怪物，但如果你不是训练师，这些怪物对你来说可能非常危险。你可能想找到完全没有怪物的安全地点！

将我们的世界视为一个网格，其中某些格子已被怪物占据。我们定义一个安全正方形为一个与网格对齐的 $D \times D$ 的正方形（$D \ge 1$），且该正方形内不包含任何怪物。你的任务是计算在整个世界中有多少个（任意大小的）安全正方形。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $R$、$C$ 和 $K$。网格有 $R$ 行 $C$ 列，包含 $K$ 个怪物。接下来 $K$ 行，每行包含两个整数 $R_i$ 和 $C_i$，表示第 $i$ 个怪物所在的行和列。（行从上到下编号，从 $0$ 开始；列从左到右编号，从 $0$ 开始。）

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是该测试用例中安全正方形的总数。

2
3 3 1
2 1
4 11 12
0 1
0 3
0 4
0 10
1 0
1 9
2 0
2 4
2 9
2 10
3 4
3 10

Case #1: 10
Case #2: 51

提示

样例 #1 的网格为：

0 0 0
0 0 0
0 1 0

这里，0 表示没有怪物的格子，1 表示有怪物的格子。共有 $10$ 个安全正方形：$8$ 个 $1\times 1$ 和 $2$ 个 $2\times 2$。

样例 #2 的网格为：

0 1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1 0
1 0 0 0 1 0 0 0 0 1 1
0 0 0 0 1 0 0 0 0 0 1

请注意，样例 #2 只会出现在大数据集中。它有 $51$ 个安全正方形：$32$ 个 $1\times 1$，$13$ 个 $2\times 2$，$5$ 个 $3\times 3$，以及 $1$ 个 $4\times 4$。

限制条件

$1 \le T \le 20$。

对于 $i \ne j$，有 $(R_i, C_i) \ne (R_j, C_j)$。（没有两个怪物在同一个格子内。）

$0 \le R_i < R$，$i = 1 \dots K$。

$0 \le C_i < C$，$i = 1 \dots K$。

小数据集（测试集 1 – 可见）

$1 \le R \le 10$。

$1 \le C \le 10$。

$0 \le K \le 10$。

大数据集（测试集 2 – 隐藏）

$1 \le R \le 3000$。

$1 \le C \le 3000$。

$0 \le K \le 3000$。

翻译由 DeepSeek V4 Pro 完成