Bugs Integrated, Inc.

Bugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six-terabyte Q-RAM chip. Each chip consists of six unit squares arranged as a $2 \times 3$ rectangle.

Q-RAM chips are made as follows. First take a rectangular silicon plate divided into $N \times M$ unit squares. Then every square is carefully tested and the defective ones are marked with a black marker.

Finally the plate is cut into memory chips. Each chip consists of $2 \times 3$ (or $3 \times 2$) unit squares, and no chip may contain any defective (marked) square. It might not be possible to cut the plate so that every good square is part of some chip. The company wants to waste as few good squares as possible, so they would like to know how to cut the plate to produce the maximum possible number of chips.

You are given the dimensions of several silicon plates together with the list of all defective squares for each plate. Write a program that, for each plate, computes the maximum number of chips that can be cut from it.

The first line contains a single integer $D$ ($1 \le D \le 5$), the number of silicon plates. $D$ blocks follow, each describing one plate.

The first line of each block contains three integers $N$ ($1 \le N \le 150$), $M$ ($1 \le M \le 10$), and $K$ ($0 \le K \le N \cdot M$), separated by single spaces. $N$ is the length of the plate, $M$ is its height, and $K$ is the number of defective squares on the plate.

The next $K$ lines list the defective squares. Each line contains two integers $x$ and $y$ ($1 \le x \le N$, $1 \le y \le M$), the coordinates of one defective square. The upper-left square has coordinates $[1, 1]$ and the bottom-right square has coordinates $[N, M]$.

For each plate, output a single line containing the maximum number of memory chips that can be cut from it.

The figure above illustrates an example of cutting a plate into chips.