SP3007 OILCOMP - Oil Company

Irving & Cohen 石油公司计划在一片区域内开发一个新的油田。他们已经进行了初步调查，并绘制了详细的网格地图，该地图显示了该地区的石油储量。 为了减少火灾蔓延的风险，他们决定在这个地图上规划建造采矿工厂，但任何两个工厂不能建在相邻的网格块上。若两个网格块有共同的边，则它们被视为相邻的。作为公司团队中的一员，你的任务是编写一个程序，根据储量地图计算出可开采石油的最大总量。

第一行输入一个整数 $N$，表示测试用例的数量。接下来有 $N$ 个测试用例，每个测试用例格式如下： ``` W H r1,1 r2,1 ... rW,1 ... r1,H r2,H ... rW,H ``` 测试用例的第一行包含两个整数 $W$ 和 $H$（$1 \le W, H \le 20$），分别表示区域的宽度和高度。接下来的 $H$ 行，每行有 $W$ 个整数，表示该区域的储量地图。每个整数 $r_{x,y}$（$0 \le r_{x,y} < 10000$）表示坐标为 $(x, y)$ 的网格块中石油的储量。

对于每个测试用例，输出格式为：第几组测试用例，以及在满足要求下可开采的最大石油量。请参阅样例输出了解具体格式。 **本翻译由 AI 自动生成**