Problem
You are organizing an international dancing competition. You have already obtained all of the following:

• A dance floor with R rows and C columns, consisting of unit square cells;
• R × C competitors;
• A cutting-edge automated judge for the competition.
  But you are still missing an audience! You are worried that the competition might not be interesting enough, so you have come up with a way to calculate the interest level for the competition.

Each competitor occupies one square unit cell of the floor and stays there until they are eliminated. A compass neighbor of a competitor x is another competitor y chosen such that y shares a row or column with x, and there are no competitors still standing in cells in between x and y. Each competitor may have between 0 and 4 compass neighbors, inclusive, and the number may decrease if all the other competitors in one orthogonal direction are eliminated.

The competition runs one round at a time. In between rounds i and i+1, if a competitor d had at least one compass neighbor during round i, and d’s skill level is strictly less than the average skill level of all of d’s compass neighbors, d is eliminated and is not part of the competition for rounds i+1, i+2, i+3, etc. Notice that d still counts as a neighbor of their other compass neighbors for the purpose of other eliminations that may also happen between rounds i and i+1. Competitors that do not have any compass neighbors are never eliminated. If after a round no competitor is eliminated, then the competition ends.

The interest level of a round is the sum of skill levels of the competitors dancing in that round (even any competitors that are to be eliminated between that round and the next). The interest level of the competition is the sum of the interest levels of all of the rounds.

Given the skill levels of the dancers that are on the floor for the first round, what is the interest level of the competition?

Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing two integers R and C. Then, there are R more lines containing C integers each. The j-th value on the i-th of these lines, $S_{i,j}$ , represents the skill level of the dancer in the cell in the i-th row and j-th column of the floor.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the interest level of the competition.

Limits
Time limit: 40 seconds per test set.
Memory limit: 1GB.
$1 ≤ S_{i,j} ≤ 10^6$ , for all i and j.

Test set 1 (Visible Verdict)
1 ≤ T ≤ 100.
1 ≤ R × C ≤ 100.

Test set 2 (Hidden Verdict)
10 ≤ T ≤ 100.
$1000 < R × C ≤ 10^5$ , in exactly 10 cases.
1 ≤ R × C ≤ 1000, in exactly T - 10 cases.

Sample

Input

4
1 1
15
3 3
1 1 1
1 2 1
1 1 1
1 3
3 1 2
1 3
1 2 3

Output
Case #1: 15
Case #2: 16
Case #3: 14
Case #4: 14

In Sample Case #1, only one competitor is on the floor. Since the competitor does not have any compass neighbors, they dance in one round, and then the competition is over. Thus the answer is equal to the dancer’s skill level, 15.

In Sample Case #2, the interest level of the first round is 1+1+1+1+2+1+1+1+1=10.

The competitors that are not in the center nor in a corner have a skill level of 1, but the average of their compass neighbors is 4 / 3, which is greater than 1, so they are eliminated. The floor during the second round looks like this:

1 . 1
. 2 .
1 . 1
This round is the last one. The competitors in the corner have two compass neighbors each, but the average of their skill level is equal to their own. The competitor in the center has no compass neighbor. The interest level of the round is 1+1+2+1+1=6. This means the interest level of the competition is 10+6=16.

In Sample Case #3, the competitor with skill level 1 is eliminated after the first round, while the other two remain. In the second round, the two other competitors become compass neighbors, and this causes the competitor with skill level 2 to be eliminated. There is a single competitor in the third round, which makes it the last one. The interest levels of the rounds are 6, 5 and 3, making the interest level of the competition 14.

/*
主要思路：不用真的删去矩阵中的邻居，而是将其表示出来，实时更新
用一个数组记录还留下的点中会变动的点的坐标，实时更新
只有在前一轮中，邻居出现变动的数，才会在下一轮有可能出现变动，每回合只需计算这些点

*/
/**
 *    author:  tourist
 *    created: 11.04.2020 04:05:41       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  for (int qq = 1; qq <= tt; qq++) {
    cout << "Case #" << qq << ": ";
    int h, w;
    cin >> h >> w;
    vector<vector<int>> a(h, vector<int>(w));
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        cin >> a[i][j];
      }
    }

    //以下一段用于获取点ij的邻居的坐标
    vector<vector<int>> when(h, vector<int>(w, -1));//记录这个点的删除时间，初始化为-1
    vector<vector<int>> up(h, vector<int>(w));
    vector<vector<int>> down(h, vector<int>(w));
    vector<vector<int>> left(h, vector<int>(w));
    vector<vector<int>> right(h, vector<int>(w));
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        up[i][j] = i - 1;
        down[i][j] = i + 1;
        left[i][j] = j - 1;
        right[i][j] = j + 1;
      }
    }//0上，1下，2左，3右
    auto GetNeighbor = [&](pair<int, int> p, int dir) {
      if (dir == 0) return make_pair(up[p.first][p.second], p.second);
      if (dir == 1) return make_pair(down[p.first][p.second], p.second);
      if (dir == 2) return make_pair(p.first, left[p.first][p.second]);
      return make_pair(p.first, right[p.first][p.second]);
    };


    long long total = 0;//记录目前舞者level的总和
    vector<pair<int, int>> check;//储存需要check是否变动的舞者坐标
    //第一次check时为所有的点
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        total += a[i][j];
        check.emplace_back(i, j);
      }
    }
    long long ans = total;

    for (int iter = 0; ; iter++) {//不停循环直到无人被删除
      vector<pair<int, int>> rm;//待删除名单
      for (auto& p : check) {
        int sum = 0;
        int cnt = 0;
        for (int dir = 0; dir < 4; dir++) {
          auto q = GetNeighbor(p, dir);//把附近四个邻居找到
          int qi = q.first;
          int qj = q.second;
          if (qi >= 0 && qj >= 0 && qi < h && qj < w) {
            sum += a[qi][qj];
            cnt += 1;
          }
        }
        if (sum > a[p.first][p.second] * cnt) {
          rm.push_back(p);//若小于周围四个的平均值则加入删除列表
        }
      }
      if (rm.empty()) {
        break;//若无人被删除则结束迭代
      }
      for (auto& p : rm) {
        when[p.first][p.second] = iter;//删除时间更新为本轮次
        total -= a[p.first][p.second];//删除本次迭代里被删除的舞者的level
      }
      ans += total;//记录到现在为止的答案总和

      vector<pair<int, int>> new_check;
      for (auto& p : rm) {
        for (int dir = 0; dir < 4; dir++) {
          auto q = GetNeighbor(p, dir);//把被删除者的邻居找到
          int qi = q.first;
          int qj = q.second;
          if (qi >= 0 && qj >= 0 && qi < h && qj < w) {
            if (when[qi][qj] != iter) {//如果它没在本轮被删除或没被遍历过
              new_check.emplace_back(qi, qj);//则加入还留下来的列表里
              when[qi][qj] = iter;//记录为被遍历过
            }
          }
        }
      }
      //若被删除的点的上下左右邻居存在，则更新其周围邻居在它被删除后的新邻居
      //与链表的结点删除类似
      for (auto& p : rm) {
        int i = p.first;
        int j = p.second;
        if (up[i][j] != -1) {
          down[up[i][j]][j] = down[i][j];
        }
        if (down[i][j] != h) {
          up[down[i][j]][j] = up[i][j];
        }
        if (left[i][j] != -1) {
          right[i][left[i][j]] = right[i][j];
        }
        if (right[i][j] != w) {
          left[i][right[i][j]] = left[i][j];
        }
      }
      swap(check, new_check);//更新还留下来的舞者坐标
    }
    cout << ans << '\n';
  }
  return 0;
}