Bejeweled™ is a classic puzzle game where the player tries to match three-in-a-row in a 2D grid of tiles by swapping pairs of adjacent tiles.

Isblinged™ is Hacker Cup's spinoff, played on a grid of $R$ rows by $C$ columns of tiles. The tile at $(i, j)$ is of an integer type $G_{i,j}$. A group refers to three or more tiles of the same type, connected directly or indirectly via the four orthogonal directions (left, right, up, and down). Initially, the given grid $G$ may already contain groups.

The player may swap two orthogonally adjacent tiles of different types. If the swap results in either tile being in a group of three or more tiles, then all tiles in the newly-formed group(s) are cleared.

For the example below (sample case 2), swapping the first two tiles in row $1$ would clear $9$ tiles:

On the other hand, swapping the first two tiles in the second column would clear $12$ tiles;

Note that the type-3 group is not cleared because it doesn't contain a swapped tile.

Please find the sum of tiles that would be cleared over all possible theoretical swaps of ordered pairs of tiles $G_{i_1,j_1}$ and $G_{i_2,j_2}$ such that $|i_1-i_2|+|j_1-j_2|=1$ and $G_{i_1,j_1} \ne G_{i_2,j_2}$.

Constraints

• $1 \le T \le 105$
• $1 \le R, C \le 3000$
• $1 \le G_{i,j} \le 10^9$
• The sum of $R*C$ across all test cases is at most $40{,}000{,}000$.

Input Format

Input begins with an integer $T$, the number of cases. For each case, there is first a line containing two space-separated integers, $R$ and $C$. Then, $R$ lines follow, the $i$th of which contains $C$ space-separated integers $G_{i,1..C}$.

Output Format

For the $i$th case, print a line containing "Case #i:" followed by a single integer, the sum of tiles that can be cleared with a single swap.

Sample

Sample Input

3
2 3
1 1 2
1 2 3
3 5
1 2 1 1 1
1 1 2 2 1
1 3 3 3 1
4 4
1 1 1 4
1 2 1 1
3 2 3 4
3 2 2 2

Sample Output

Case #1: 12
Case #2: 112
Case #3: 74

Sample Explanation

In the first sample case:

• $G_{1,1}$, $G_{1,3}$, and $G_{2,3}$ can't be swapped with anything that leads to any tiles being cleared.
• $G_{1,2}$ can be swapped with the type-2 tile below to clear $3$ tiles.
• $G_{2,1}$ can be swapped with the type-2 tile below to clear $3$ tiles.
• $G_{2,2}$ can be swapped with either the type-1 cell above or to the left, each clearing $3$ tiles.

The answer is therefore $3+3+2*3+12$.

In the second sample case, the unordered pairs of swaps clearing non-zero numbers of tiles are:

• $G_{1,1} \leftrightarrow G_{1,2}$: clearing $9$ tiles
• $G_{1,2} \leftrightarrow G_{1,3}$: clearing $5+3=8$ tiles
• $G_{1,2} \leftrightarrow G_{2,1}$: clearing $9+3=12$ tiles
• $G_{1,3} \leftrightarrow G_{2,3}$: clearing $5$ tiles
• $G_{1,4} \leftrightarrow G_{2,4}$: clearing $4$ tiles
• $G_{2,2} \leftrightarrow G_{2,3}$: clearing $6$ tiles
• $G_{2,2} \leftrightarrow G_{3,2}$: clearing $4$ tiles
• $G_{2,4} \leftrightarrow G_{2,5}$: clearing $4$ tiles
• $G_{3,1} \leftrightarrow G_{3,2}$: clearing $4$ tiles

Doubling the sum for ordered pairs, we get $2*(9+8+12+5+4+6+4+4+4) = 112$.