Safe Squares (Large)

Monster trainers go looking for monsters, but a monster is dangerous to anyone who is not a trainer. You want to find safe spots that hold no monsters.

Think of the world as a grid. Some cells hold one monster each. A safe square is a grid-aligned square region of $D \times D$ cells that contains no monster at all ($D \ge 1$). Count how many safe squares of any size the whole world has. Two squares of the same size at different positions count separately.

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

Each test case starts with a line holding three integers $R$, $C$, and $K$. The grid has $R$ rows and $C$ columns and holds $K$ monsters. Each of the next $K$ lines holds the row $R_i$ and the column $C_i$ of the $i$-th monster. Rows are numbered from top to bottom starting at 0, and columns 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 number of safe squares in that test case.

• $1 \le T \le 20$
• $1 \le R \le 3000$
• $1 \le C \le 3000$
• $0 \le K \le 3000$
• $0 \le R_i < R$ ($1 \le i \le K$)
• $0 \le C_i < C$ ($1 \le i \le K$)
• $(R_i, C_i) \ne (R_j, C_j)$ for $i \ne j$. No cell holds more than one monster.