Maximizing Q-RAM Chip Production

Bugs Integrated, Inc. is a leading manufacturer of advanced memory chips. They are starting production of a new $6$ TB Q-RAM chip. Each chip consists of 6 square silicon blocks arranged in a $2\times3$ (or $3\times2$) rectangle. A silicon wafer is produced by dividing a large rectangular silicon ingot into an $N\times M$ grid of square blocks. Each block is tested carefully; defective blocks are marked black.

After testing, the wafer is cut into memory chips. Each chip must be a contiguous rectangle of blocks of size either $2\times3$ or $3\times2$ and must not include any defective blocks. It is not necessary that every good block is used in some chip. The company wishes to minimize the wastage of good blocks, so they want to know how to cut the wafer so as to maximize the number of chips produced.

Your task is to determine, for each wafer, the maximum number of chips that can be obtained.

inputFormat

The input begins with an integer $T$, the number of test cases. For each test case, the first line contains two integers $N$ and $M$ (the dimensions of the wafer). The next line contains an integer $K$, the number of defective (bad) blocks. Each of the next $K$ lines contains two integers $r$ and $c$, indicating that the block in row $r$ and column $c$ (1-indexed) is defective.

It is guaranteed that $1 \le T \le 10$, and $1 \le N, M \le 10$. (The constraints are small so that a backtracking solution is feasible.)

outputFormat

For each test case, output a single integer — the maximum number of chips that can be cut from the wafer.

sample

1
2 3
0

1