Description

你正在组织一场国际舞蹈比赛。目前已经准备好以下内容：

• 一个由 $\mathbf{R}$ 行 $\mathbf{C}$ 列单位方格组成的舞池；
• $\mathbf{R} \times \mathbf{C}$ 名参赛选手；
• 一套先进的自动评分系统。

但你还缺少观众！担心比赛可能不够精彩，你设计了一种计算比赛精彩度的方法。

每名选手占据舞池的一个单位方格，直到被淘汰为止。选手 $\mathrm{x}$ 的罗盘邻居是指满足以下条件的另一选手 $\mathrm{y}$：$\mathrm{y}$ 与 $\mathrm{x}$ 同行或同列，且 $\mathrm{x}$ 与 $\mathrm{y}$ 之间没有其他未被淘汰的选手。每名选手可能有 0 到 4 个罗盘邻居（包含边界），且数量会因某一方向上选手被淘汰而减少。

比赛按轮次进行。在第 $\mathrm{i}$ 轮和第 $\mathrm{i}+1$ 轮之间，若选手 $\mathrm{d}$ 在第 $\mathrm{i}$ 轮时有至少一个罗盘邻居，且 $\mathrm{d}$ 的技能值严格小于其所有罗盘邻居技能值的平均值，则 $\mathrm{d}$ 被淘汰，不再参与后续轮次。注意：$\mathrm{d}$ 在被淘汰前仍会作为其他选手的罗盘邻居参与淘汰判定。没有罗盘邻居的选手永远不会被淘汰。若某一轮后无人被淘汰，则比赛结束。

每一轮的精彩度是该轮所有参赛选手（包括即将被淘汰者）技能值之和。比赛的总精彩度是所有轮次精彩度的总和。

给定第一轮所有选手的技能值，求比赛的总精彩度。

Input Format

输入第一行包含测试用例数量 $\mathrm{T}$。随后是 $\mathrm{T}$ 个测试用例，每个用例格式如下：

• 第一行：两个整数 $\mathbf{R}$ 和 $\mathbf{C}$；
• 接下来 $\mathbf{R}$ 行：每行 $\mathbf{C}$ 个整数，其中第 $\mathrm{i}$ 行第 $\mathrm{j}$ 列的 $\mathrm{S}_{\mathrm{i}, \mathrm{j}}$ 表示初始位于第 $\mathrm{i}$ 行第 $\mathrm{j}$ 列选手的技能值。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $\mathrm{x}$ 为测试用例编号（从 1 开始），$\mathrm{y}$ 为比赛的总精彩度。

4
1 1
15
3 3
1 1 1
1 2 1
1 1 1
1 3
3 1 2
1 3
1 2 3

Case #1: 15
Case #2: 16
Case #3: 14
Case #4: 14

Hint

样例解释

• 样例 #1：仅有一名选手。因其无罗盘邻居，比赛仅进行一轮，总精彩度为该选手技能值 15。

• 样例 #2：

  • 第一轮精彩度：$1+1+1+1+2+1+1+1+1=10$。
  • 非中心且非角落的选手（技能值 1）因邻居平均值 $4/3 > 1$ 被淘汰。第二轮舞池如下：

    1 . 1
    . 2 .
    1 . 1
    

  • 角落选手的邻居平均值等于自身技能值，中心选手无邻居，比赛结束。第二轮精彩度 $1+1+2+1+1=6$，总精彩度 $10+6=16$。

• 样例 #3：

  • 第一轮后技能值 1 的选手被淘汰，剩余两人。
  • 第二轮中，技能值 2 的选手因邻居平均值 $3/1 > 2$ 被淘汰。
  • 第三轮仅剩一人，比赛结束。各轮精彩度分别为 6、5、3，总精彩度 14。

数据范围

• $\forall i,j$，$1 \leqslant S_{i, j} \leqslant 10^{6}$。

测试集 1（9 分，可见评测结果）

• $1 \leqslant \mathrm{T} \leqslant 100$；
• $1 \leqslant \mathrm{R} \times \mathrm{C} \leqslant 100$。

测试集 2（28 分，隐藏评测结果）

• $10 \leqslant \mathrm{T} \leqslant 100$；
• 恰好 10 个用例满足 $1000 < \mathrm{R} \times \mathrm{C} \leqslant 10^{5}$；
• 其余 $\mathrm{T}-10$ 个用例满足 $1 \leqslant \mathrm{R} \times \mathrm{C} \leqslant 1000$。

翻译由 DeepSeek V3 完成