스퀘어 댄스

당신은 국제 댄스 대회를 준비하고 있다. 다음 항목은 이미 모두 준비했다.

• 단위 정사각형 칸들로 이루어진 R행 C열의 무대;

• R × C명의 참가자;

• 대회를 위한 최첨단 자동 심판.

하지만 아직 관객이 없다! 대회가 충분히 흥미롭지 않을까 걱정되어, 대회의 흥미도를 계산하는 방법을 생각해 냈다.

각 참가자는 무대의 한 단위 정사각형 칸을 차지하며 탈락할 때까지 그곳에 머문다. 참가자 x의 나침반 이웃은 x와 같은 행이나 열에 있고, x와 자신 사이의 칸에 아직 남아 있는 참가자가 없는 다른 참가자 y이다. 각 참가자에게는 0명 이상 4명 이하의 나침반 이웃이 있을 수 있으며, 한 직교 방향에 있는 다른 참가자들이 모두 탈락하면 그 수가 줄어들 수 있다.

대회는 한 번에 한 라운드씩 진행된다. i번째 라운드와 i+1번째 라운드 사이에, 참가자 d에게 i번째 라운드 동안 적어도 하나의 나침반 이웃이 있었고 d의 실력 수준이 d의 모든 나침반 이웃의 평균 실력 수준보다 엄격히 낮다면, d는 탈락하여 i+1, i+2, i+3번째 등의 라운드에서 대회에 참가하지 않는다. i번째 라운드와 i+1번째 라운드 사이에 함께 일어날 수 있는 다른 탈락을 판정할 때에는 d도 자신의 다른 나침반 이웃들에게 여전히 이웃으로 간주된다는 점에 유의하라. 나침반 이웃이 하나도 없는 참가자는 절대 탈락하지 않는다. 한 라운드가 끝난 뒤 아무 참가자도 탈락하지 않으면 대회가 끝난다.

한 라운드의 흥미도는 그 라운드에서 춤추는 참가자들의 실력 수준의 합이다(그 라운드와 다음 라운드 사이에 탈락할 참가자도 모두 포함한다). 대회의 흥미도는 모든 라운드의 흥미도의 합이다.

첫 라운드에 무대 위에 있는 무용수들의 실력 수준이 주어질 때, 대회의 흥미도는 얼마인가?

제한

시간 제한: 테스트 세트당 40초. 메모리 제한: 1GB. 모든 i와 j에 대해 1 ≤ $S_{i,j}$ ≤ $10^{6}$.

테스트 세트 1 (공개 판정)

1 ≤ T ≤ 100. 1 ≤ R × C ≤ 100.

테스트 세트 2 (비공개 판정)

10 ≤ T ≤ 100. 정확히 10개의 케이스에서 1000 < R × C ≤ $10^{5}$. 정확히 T - 10개의 케이스에서 1 ≤ R × C ≤ 1000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 R과 C가 포함된 줄로 시작한다. 이어서 각각 C개의 정수를 포함하는 R개의 줄이 더 주어진다. 이 줄들 중 i번째 줄의 j번째 값 $S_{i, j}$는 무대의 i번째 행 j번째 열에 있는 칸의 무용수의 실력 수준을 나타낸다.

각 테스트 케이스에 대해 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(번호는 1부터 시작한다), y는 대회의 흥미도이다.

예제 케이스 #1에서는 무대에 참가자가 단 한 명만 있다. 이 참가자에게는 나침반 이웃이 하나도 없으므로 한 라운드 동안 춤을 추고, 그 뒤 대회가 끝난다. 따라서 답은 무용수의 실력 수준인 15와 같다.

예제 케이스 #2에서 첫 라운드의 흥미도는 1+1+1+1+2+1+1+1+1=10이다.

중앙이나 모서리에 있지 않은 참가자들의 실력 수준은 1이지만, 이들의 나침반 이웃의 평균은 4 / 3로 1보다 크므로 이들은 탈락한다. 두 번째 라운드의 무대는 다음과 같다.

이 라운드가 마지막 라운드이다. 모서리에 있는 참가자들은 각각 두 명의 나침반 이웃이 있지만, 그 이웃들의 평균 실력 수준은 자신의 실력 수준과 같다. 중앙의 참가자에게는 나침반 이웃이 없다. 이 라운드의 흥미도는 1+1+2+1+1=6이다. 따라서 대회의 흥미도는 10+6=16이다.

예제 케이스 #3에서는 실력 수준이 1인 참가자가 첫 라운드 뒤에 탈락하고, 다른 두 참가자는 남는다. 두 번째 라운드에서 다른 두 참가자는 서로 나침반 이웃이 되고, 이로 인해 실력 수준이 2인 참가자가 탈락한다. 세 번째 라운드에는 참가자가 한 명뿐이므로 이 라운드가 마지막 라운드가 된다. 각 라운드의 흥미도는 6, 5, 3이며, 대회의 흥미도는 14이 된다.