비

바다에 섬이 하나 있다. 이 섬은 R개의 행과 C개의 열로 이루어진 행렬로 나타낼 수 있으며, H[i][j]는 각 단위 칸의 높이를 나타낸다. 다음은 3*3 섬의 예이다:

3 5 5
5 4 5
5 5 5

때때로 이 섬의 모든 칸에 폭우가 고르게 내린다. 임의로 많은 양의 물이 내린다고 가정해도 된다. 이러한 폭우가 내린 뒤에는 섬의 일부 영역(변을 따라 이어진 하나 이상의 단위 칸으로 이루어진 영역)에 물이 고일 수 있다. 이는 그 영역의 어떤 칸이 영역 밖의 칸과 변(꼭짓점만이 아님)을 공유하는 모든 곳에서, 그 영역 밖의 칸의 높이가 더 큰 경우에만 일어날 수 있다. (주변 바다는 높이가 0인 칸들로 이루어진 무한한 격자로 간주한다.) 그렇지 않으면 물은 항상 인접한 하나 이상의 영역으로 흘러가고(이 문제에서는 어느 영역으로 흐르는지는 중요하지 않다), 결국 바다로 빠져나간다. 바다의 높이는 절대 변하지 않는다고 가정해도 된다. 폭우가 내린 뒤 섬의 칸들의 높이를 W[i][j]로 나타낸다. 다음은 폭우가 내린 뒤 예시 섬의 높이이다. 초기 높이가 4인 칸은 초기 높이가 더 큰 칸들과만 인접하므로 그 칸에 물이 고여 높이가 5까지 올라간다. 그 뒤에는 더 높은 칸들로 둘러싸인 영역이 더 이상 없으므로 물도 더 이상 고이지 않는다. 다시 말하지만, 꼭짓점에서만 만나는 칸들 사이로는 물이 직접 흐를 수 없으며, 물은 반드시 공유하는 변을 따라 흘러야 한다. 다음은 비가 내린 뒤 예시 섬의 높이이다:

3 5 5
5 5 5
5 5 5

섬의 행렬이 주어질 때, 폭우가 내린 뒤 증가한 높이의 총합 sum(W[i][j]-H[i][j])을 계산할 수 있는가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ H[i][j] ≤ 1000.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ R ≤ 10. 1 ≤ C ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ R ≤ 50. 1 ≤ C ≤ 50.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 섬에 있는 칸들의 행과 열의 수를 나타내는 두 수 R과 C가 주어진다. 그다음에는 각각 C개의 양의 정수로 이루어진 R개의 줄이 주어진다. 이 줄들 중 i번째 줄의 j번째 값은 H[i][j], 즉 i번째 행 j번째 열에 있는 칸의 높이를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 증가한 높이의 총합이다.

케이스 1은 문제 설명에서 설명했다.

케이스 2에서 비가 내린 뒤 섬의 모습은 다음과 같다:

케이스 3는 비가 내린 뒤에도 변하지 않는다.