Rain (Small)

There is an island in the sea. The island is described as a matrix with $R$ rows and $C$ columns, where $H[i][j]$ is the height of each unit cell. Here is an example of a 3 by 3 island:

3 5 5
5 4 5
5 5 5

Sometimes a heavy rain falls evenly on every cell of this island. You can assume that an arbitrarily large amount of water falls. After such a heavy rain, some areas of the island (each formed of one or more unit cells joined along edges) might collect water. This happens only if, wherever a cell in that area shares an edge (not just a corner) with a cell outside of that area, the cell outside of that area has a larger height. The surrounding sea counts as an infinite grid of cells with height 0. Otherwise, water always flows away into one or more of the neighboring areas (it does not matter which) and eventually out to sea. You may assume that the height of the sea never changes.

Let $W[i][j]$ be the height of each cell after a heavy rain. In the example, the cell with initial height 4 borders only cells with higher initial heights, 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. Again, water cannot flow directly between cells that meet only at a corner; water 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

As another example, consider this island:

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

After the rain it looks like this:

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

The cell of height 2 in the bottom row shares an edge with the sea, so no water collects in it. The three cells of height 1 above it fill up to height 2, so the total increase is 3.

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

The first line of the input gives 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 cells on the island. Then come $R$ lines of $C$ positive integers each. The $j$-th value on the $i$-th of these lines is $H[i][j]$, the height of the cell in the $i$-th row and the $j$-th column.

Limits

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

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 total increase in height.