Rain (Large)

There is an island in the sea. The island is a grid with $R$ rows and $C$ columns, and $H[i][j]$ is the height of the cell in row $i$ and column $j$. Here is an example of an island with 3 rows and 3 columns:

3 5 5
5 4 5
5 5 5

Sometimes a heavy rain falls evenly on every cell of the island. Assume that an arbitrarily large amount of water falls. After such a rain, some areas of the island (one or more cells joined along edges) might collect water. This can happen only if, wherever a cell in the area shares an edge with a cell outside the area, the cell outside the area is higher. Cells that touch only at a corner do not share an edge. The sea around the island counts as an infinite grid of cells with height 0. If an area does not meet this condition, its water flows into one or more neighboring areas and eventually out to sea (for this problem, it does not matter which way). Assume that the height of the sea never changes.

Let $W[i][j]$ be the height of each cell after the rain. In the example, the cell with initial height 4 borders only cells that are higher, so water collects in it and raises its height to 5. After that, no area is surrounded by higher cells, so no more water collects. Note again that water cannot flow directly between cells that meet only at a corner; it must flow along shared edges. Here are the heights of the example island after the rain:

3 5 5
5 5 5
5 5 5

Given the heights of the island, compute the total increase in height after the rain, $\sum (W[i][j] - H[i][j])$.

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains two integers $R$ and $C$, the number of rows and columns of the island. Each of the next $R$ lines contains $C$ positive integers. The $j$-th number on the $i$-th of these lines is $H[i][j]$, the height of the cell in row $i$ and column $j$.

Limits

• $1 \le T \le 100$
• $1 \le H[i][j] \le 1000$
• $1 \le R \le 50$
• $1 \le C \le 50$

For each test case, output one line in the form Case #x: y, where x is the test case number (starting from 1) and y is the total increase in height after the rain.

Case 1 of the sample input is the island described in the statement.

In case 2, the island looks like this after the rain:

5 5 5 1
5 2 2 5
5 2 5 5
5 2 5 8

Case 3 does not change after the rain.