토끼의 집

Barbara는 작년에 학교에서 성적이 매우 좋았기 때문에, 부모님은 애완용 토끼를 선물하기로 했다. Barbara는 매우 신이 나서 토끼를 위한 집을 지었으며, 이 집은 $\mathbf{R}$개의 행과 $\mathbf{C}$개의 열로 이루어진 2D 격자로 볼 수 있다.

토끼는 뛰어오르는 것을 좋아하므로, Barbara는 격자의 여러 칸에 상자를 여러 개 쌓았다. 각 상자는 모든 변의 길이가 같고 그 크기가 격자 한 칸의 크기와 정확히 일치하는 정육면체이다.

하지만 Barbara는 곧 토끼가 $1$개 상자보다 높은 높이를 뛰어오르는 것은 위험할 수 있다는 사실을 깨닫고, 집을 일부 조정하여 이를 방지하기로 한다. Barbara는 인접한 모든 칸 쌍의 높이 차이의 절댓값이 최대 $1$개 상자가 되기를 바란다. 두 칸이 한 변을 공유하면 인접한 것으로 간주한다.

모든 상자가 강력 접착제로 붙어 있기 때문에 Barbara는 처음부터 있던 상자를 제거할 수 없지만, 그 위에 상자를 추가할 수는 있다. Barbara는 원하는 만큼 많은 칸에 원하는 만큼 많은 상자를 추가할 수 있으며, 추가하는 칸이나 상자의 수가 없을 수도 있다. 토끼의 집이 안전해지도록 추가해야 하는 상자 총개수의 최솟값을 구하도록 도와주자.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$, $j$에 대해 $0 \le \mathbf{G_{i,j}} \le 2 \cdot 10^6$.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{R}, \mathbf{C} \le 50$.

테스트 세트 2

시간 제한: 40초. $1 \le \mathbf{R}, \mathbf{C} \le 300$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 정수 $\mathbf{R}$와 $\mathbf{C}$를 포함하는 줄로 시작한다.

이어서 각각 $\mathbf{C}$개의 정수를 포함하는 $\mathbf{R}$개의 줄이 주어진다. $i$번째 줄의 $j$번째 정수 $\mathbf{G_{i,j}}$는 격자의 $i$번째 행과 $j$번째 열에 있는 칸에 처음에 놓인 상자의 개수를 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$은 토끼의 집이 안전해지도록 추가해야 하는 상자의 최소 개수이다.

예제 케이스 #1에서는 인접한 모든 칸 쌍의 높이 차이의 절댓값이 이미 최대 $1$개 상자이므로, 상자를 추가할 필요가 없다.

예제 케이스 #2에서는 가장 왼쪽 칸과 가운데 칸의 높이 차이의 절댓값이 $3$개 상자이다. 이를 바로잡기 위해 가운데 칸에 $2$개의 상자를 추가할 수 있다. 하지만 그러면 가운데 칸과 가장 오른쪽 칸의 높이 차이의 절댓값이 $2$개 상자가 되므로, Barbara는 가장 오른쪽 칸에 $1$개의 상자를 추가하여 이를 바로잡을 수 있다. 이 $3$개의 상자를 추가하면 안전 조건이 충족된다.

예제 케이스 #3에서는 격자 가운데 칸과 그 칸에 인접한 네 칸 모두의 높이 차이의 절댓값이 $2$개 상자이다. 한 가지 방법은 가운데 칸에 인접한 모든 칸에 정확히 $1$개의 상자를 추가하여, 인접한 모든 칸 쌍의 높이 차이의 절댓값이 최대 $1$개 상자가 되게 하는 것이다. 이 방법에는 총 $4$개의 상자가 필요하다.