MineLayer 是一款类似于扫雷的益智游戏，在 $R \times C$ 的网格上进行。网格中的每个方格要么包含一个地雷，要么没有地雷。MineLayer 谜题由一个数字网格组成，每个数字表示其所有相邻方格以及该方格本身所包含的地雷总数。因此，这些数字的范围从 0 到 9。

MineLayer 的目标是找出一种与给定线索相匹配的地雷布局。

下面是一个典型的 $3 \times 4$ 网格。左侧是原始布局，右侧是谜题。

由于可能存在多种解，你的任务是编写一个程序，输出中间行中可能包含的最大地雷数。行数始终为奇数，且谜题始终至少有一个解。

输入格式

输入的第一行包含测试用例的数量 $N$。接下来是 $N$ 个测试用例。

每个测试用例的第一行包含两个用空格分隔的数字：$R$（行数）和 $C$（列数）。$R$ 始终为奇数。接下来的 $R$ 行，每行包含 $C$ 个用空格分隔的数字，表示该行的线索。

输出格式

对于每个测试用例，输出一行 "Case #X: Y"，其中 $X$ 是从 1 开始的用例编号，$Y$ 是满足给定约束条件的网格中间行中可能包含的最大地雷数。

数据范围

$1 \le N \le 50$。

每个谜题保证至少有一个解。

小数据集（测试集 1 - 可见；4 分）

$R = 3$ 或 $R = 5$。

$3 \le C \le 5$。

大数据集（测试集 2 - 隐藏；13 分）

$R$ 是 3 到 49 之间的奇数（包含 3 和 49）。

$3 \le C \le 49$。

样例

样例输入 1

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

样例输出 1

Case #1: 1
Case #2: 1