Mattress stain removal

Hongjun threw a party at his house over the Chuseok holiday. Many small children came, and the next morning he found several stains that had soaked through the bed sheet into the mattress. Washing the whole mattress costs too much, so Hongjun wants to buy a small stain removal tool instead.

The top surface of the mattress is a rectangular grid with $m$ rows and $n$ columns. The top left cell is $(1, 1)$ and the bottom right cell is $(m, n)$. The coordinate $(r, s)$ means the cell in row $r$ from the top and column $s$ from the left. One stain covers one cell.

The tool takes a $3 \times 3$ block of cells that lies entirely inside the mattress and erases every stain in that block at once. The sides of the block are parallel to the sides of the mattress. The tool is thrown away after one use, so one tool clears one block. Given the size of the mattress and the positions of the stains, find the smallest number of tools needed to erase every stain.

On a $6 \times 11$ mattress with stains at $(4, 3)$, $(6, 5)$, $(3, 6)$, $(4, 7)$, two tools are enough. The block spanning rows 4 to 6 and columns 3 to 5 erases $(4, 3)$ and $(6, 5)$, and the block spanning rows 2 to 4 and columns 5 to 7 erases $(3, 6)$ and $(4, 7)$.

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

The first line of each test case contains two natural numbers $m$ and $n$, the size of the mattress. ($3 \le m \le 10$, $3 \le n \le 1000$) The second line contains the number of stains $c$. ($0 \le c \le mn$) Each of the next $c$ lines contains the row number and the column number of one stain, separated by a space. The row number is between $1$ and $m$, the column number is between $1$ and $n$, and no two stains share a coordinate.

For each test case, print the smallest number of tools needed to erase every stain, one number per line.