hackercupai/hackercup huggingface dataset:
*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:

{{PHOTO_ID:1310493279783732|WIDTH:700}}

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

{{PHOTO_ID:650302073463012|WIDTH:700}}

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 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 right of it 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\).