题目描述

给定一个 $N \times M$ 的非负整数矩阵，你需要从中选出若干个格子中的数，使得任意两个被选中的格子都不相邻（若两个格子在彼此相邻的 $8$ 个方向之一上，则视为相邻）。求所有合法选取方案中，选出的数之和的最大值。

输入格式

第一行一个正整数 $T$，表示数据组数。

每组数据第一行两个正整数 $N$ 和 $M$，表示矩阵的行数和列数。

接下来 $N$ 行，每行 $M$ 个非负整数，描述矩阵内容。

输出格式

共 $T$ 行，每行一个非负整数，表示该组数据的答案。

样例

3
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1

271
172
99

</p>

提示

样例解释

对于第一组数据，一种最优取法如下：

$$\begin{matrix} [67] & 75 & 63 & 10 \\ 29 & 29 & [92] & 14 \\ [21] & 68 & 71 & 56 \\ 8 & 67 & [91] & 25 \\ \end{matrix}$$

数据范围及约定

• 对于$20\%$的数据，$1\le N, M \le 3$；
• 对于$40\%$的数据，$1\le N, M\le 4$；
• 对于$60\%$的数据，$1\le N, M\le 5$；
• 对于$100\%$的数据，$1\le N, M\le 6$，$1\le T\le 20$，$a_{i,j}\le10^5$。