Chocolate and the Friends' Raid

Coco's chocolate machine produces rectangular chocolate bars whose width and height are both multiples of 4. Coco wants to sell each $M \times N$ bar by splitting it into $1 \times 2$ or $2 \times 1$ pieces. One day, $K$ ($0 \le K \le 4$) friends came over, and each of them ate one $1 \times 1$ square from the bar. Find the maximum number of pieces Coco can get by splitting the remaining chocolate.

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

The first line of each test case contains $M$, $N$, and $K$. $M$ is the width and $N$ is the height of the chocolate. The next $K$ lines each give the position of one square a friend ate, as the column $m$ followed by the row $n$. The top-left cell is $(1, 1)$, and no two eaten positions are the same.

For each test case, print on one line the maximum number of $1 \times 2$ or $2 \times 1$ pieces that can be obtained by splitting the given chocolate.

• $1 \le T \le 1000$
• $4 \le M, N \le 1000$
• $M$ and $N$ are multiples of $4$
• $0 \le K \le 4$
• $1 \le m \le M$, $1 \le n \le N$