Description

Bugs Integrated,Inc. is a major manufacturer of high-end memory chips. They are starting production of a new $6$ TB Q-RAM chip. Each chip consists of six square silicon blocks arranged in a $2×3$ rectangle. Q-RAM chips are manufactured by cutting a large rectangular silicon wafer into $N×M$ square silicon blocks. Then all square silicon blocks are carefully tested, and the defective ones are marked in black.

Finally, the wafer is cut into memory chips. Each chip consists of $2×3$ (or $3×2$) unit square silicon blocks. Of course, no chip may contain any defective (marked) square silicon blocks. It may be impossible to cut the wafer so that every good square silicon block becomes part of some memory chip. The company wants to waste as few good square silicon blocks as possible. Therefore, they want to know how to cut the wafer to produce as many chips as possible.

You are given the sizes of several wafers and the list of all defective square silicon blocks on each wafer. Your task is to write a program that computes, for each wafer, the maximum number of chips that can be cut from it.

Input Format

The first line contains an integer $D$, the number of wafers. Then follow $D$ sections, each describing one wafer.

The first line of each section contains three integers $N$, $M$, and $K$, separated by single spaces. $N$ is the width of the wafer, $M$ is its height, and $K$ is the number of defective square silicon blocks on the wafer.

The next $K$ lines list the defective square silicon blocks. Each line contains two integers $x$ and $y$, giving the coordinates of one defective square silicon block (the top-left corner is $(1,1)$, and the bottom-right corner is $(N,M)$).

Output Format

For each wafer, output one line with the maximum number of chips that can be cut from it.

2
6 6 5
1 4
4 6
2 2
3 6
6 4
6 5 4
3 3
6 1
6 2
6 4

3
4

Hint

Constraints

For $100\%$ of the testdata, $1 \leq D \leq 5$, $1 \leq N \leq 150$, $1 \leq M \leq 10$, $0 \leq K \leq M×N$, $1 \leq x \leq N$, $1 \leq y \leq M$。

Sample Explanation

Problem Notes

From CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2002: Bugs Integrated,Inc.。
Translated and organized by @求学的企鹅。

Translated by ChatGPT 5