Safe Squares (Small)

Codejamon trainers keep hunting for monsters, but to anyone who is not a trainer those monsters are dangerous. You want to find the safe spots that hold no monster at all.

Treat the world as a grid. Some cells are occupied by monsters. A safe square is a grid aligned block of $D \times D$ cells, with $D \ge 1$, that contains no monster. Count how many safe squares of any size the whole world has.

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

Each test case starts with a line holding three integers $R$, $C$, and $K$. The grid has $R$ rows and $C$ columns and contains $K$ monsters. $K$ more lines follow. Each of them holds the row $R_i$ and the column $C_i$ of the cell where the $i$-th monster stands. Rows are numbered from top to bottom starting at 0, and columns are numbered from left to right starting at 0.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting at 1 and $y$ is the total number of safe squares in that test case.

• $1 \le T \le 20$
• $1 \le R \le 100$
• $1 \le C \le 100$
• $0 \le K \le \min(R \times C, 100)$
• $0 \le R_i < R$
• $0 \le C_i < C$
• $(R_i, C_i) \ne (R_j, C_j)$ for $i \ne j$. No two monsters share a cell.

The grid of the first test case of the example is:

0 0 0
0 0 0
0 1 0

Here 0 is a cell with no monster and 1 is a cell with a monster. It has 10 safe squares: 8 of size $1 \times 1$ and 2 of size $2 \times 2$.

The grid of the second test case is:

0 1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1 0
1 0 0 0 1 0 0 0 0 1 1
0 0 0 0 1 0 0 0 0 0 1

It has 51 safe squares: 32 of size $1 \times 1$, 13 of size $2 \times 2$, 5 of size $3 \times 3$, and 1 of size $4 \times 4$.