Rabbit House

Barbara는 작년에 학교에서 성적이 아주 좋아서, 부모님이 애완용 토끼를 선물로 주기로 했다. Barbara는 너무 신이 나서 토끼를 위한 집을 지었는데, 이 집은 R개의 행과 C개의 열로 이루어진 2차원 격자로 나타낼 수 있다.

토끼는 점프를 좋아하므로, Barbara는 격자의 여러 칸 위에 상자를 쌓았다. 상자는 모두 같은 크기의 정육면체이며, 그 크기는 격자의 한 칸과 정확히 같다.

그런데 Barbara는 토끼가 상자 1개 높이보다 큰 점프를 하면 위험할 수 있다는 사실을 곧 깨닫고, 집을 조금 손보아 그런 일이 없도록 하려 한다. Barbara는 인접한 두 칸에 대해 높이의 절댓값 차이가 상자 1개 이하이기를 바란다. 두 칸은 변을 공유하면 인접하다고 한다.

모든 상자는 순간접착제로 붙어 있어서 Barbara는 처음에 있던 상자를 하나도 치울 수 없지만, 그 위에 상자를 더 쌓을 수는 있다. 원하는 만큼 많은 칸에 원하는 만큼 많은 상자(0개일 수도 있다)를 더 쌓을 수 있다. 토끼의 집이 안전해지도록 더 쌓아야 하는 상자의 최소 총 개수를 구하라.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다.

각 테스트 케이스는 두 정수 R과 C가 들어 있는 한 줄로 시작한다.

그다음 R개의 줄이 주어지며, 각 줄에는 C개의 정수가 있다. i번째 줄의 j번째 정수 Gi,j는 격자의 i번째 행 j번째 열에 있는 칸에 처음에 놓여 있는 상자의 개수를 나타낸다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 토끼의 집이 안전해지도록 더 쌓아야 하는 상자의 최소 개수이다.

• 1 ≤ T ≤ 100.
• 모든 i, j에 대해 0 ≤ Gi,j ≤ 2⋅106.

예제 1에서는 모든 인접한 칸 쌍의 높이 절댓값 차이가 이미 상자 1개 이하이므로, 상자를 더 쌓을 필요가 없다.

예제 2에서는 가장 왼쪽 칸과 가운데 칸의 높이 절댓값 차이가 상자 3개이다. 이를 고치기 위해 가운데 칸에 상자 2개를 더 쌓을 수 있다. 그러면 가운데 칸과 가장 오른쪽 칸의 절댓값 차이가 상자 2개가 되므로, Barbara는 가장 오른쪽 칸에 상자 1개를 더 쌓아 고칠 수 있다. 이렇게 상자 3개를 더 쌓으면 안전 조건이 만족된다.

예제 3에서는 격자 가운데 칸이 인접한 네 칸 모두와 높이 절댓값 차이 2개를 가진다. 한 가지 방법은 가운데 칸에 인접한 모든 칸에 상자를 정확히 1개씩 더 쌓아, 어떤 인접한 칸 쌍의 절댓값 차이도 상자 1개 이하가 되도록 하는 것이다. 이때 상자는 모두 4개 필요하다.