Description

Given an $N\times M$ matrix of non-negative integers, you need to select some numbers such that no two selected numbers are adjacent. Two numbers are considered adjacent if one is in any of the 8 neighboring cells of the other (including diagonals). Find the maximum possible sum of the selected numbers.

Input Format

The first line contains a positive integer $T$, indicating there are $T$ test cases.

For each test case, the first line contains two positive integers $N$ and $M$, indicating the matrix has $N$ rows and $M$ columns.

The next $N$ lines each contain $M$ non-negative integers, describing the matrix.

Output Format

Output $T$ lines, each containing a single non-negative integer: the required answer.

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

Hint

Sample Explanation

For the first test case, a valid selection is as follows:

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

Constraints

• For 20% of the testdata, $1\le N, M \le 3$.
• For 40% of the testdata, $1\le N, M \le 4$.
• For 60% of the testdata, $1\le N, M \le 5$.
• For 100% of the testdata, $1\le N, M \le 6$, $1\le T \le 20$, $a_{i,j}\le 10^5$.

Translated by ChatGPT 5