题目描述

Bugs Integrated,Inc. 是高级存储芯片的主要制造商。他们正在开始生产新的 $6$ TB Q-RAM 芯片。每个芯片由以 $2×3$ 的矩形排列的六个方形硅片块组成。Q-RAM 芯片的制造方式是将一块长方形的大硅片分成 $N×M$ 个方形硅片块。然后仔细测试所有方形硅片块，坏的用黑色标记。

最后，将硅片切割成存储芯片。每个芯片由 $2×3$（或 $3×2$）单位方形硅片块组成。当然，任何芯片都不能包含任何坏的（标记的）方形硅片块。它可能不能将硅片切割成每一个好的方形硅片块都成为某些存储芯片的一部分。该公司希望尽可能少地浪费好方形硅片块。因此他们想知道如何切割硅片以尽可能多地切出芯片。
现您将获得几个硅片的尺寸和其每个硅片所有坏方形硅片块的列表。你的任务是编写一个程序，计算每个硅片最多可以从其切下的芯片数量。

输入格式

第一行由一个整数 $D$ 组成，表示硅片的数量。接下来 $D$ 个部分，每个部分描述一个硅片。每个部分的第一行包含三个整数 $N$，$M$，$K$，其间由单个空格分隔。$N$ 是硅片的长度，$M$ 是它的高度，$K$ 是硅片中坏方硅片块的数量。以下 $K$ 行包含一个坏方硅片块列表。每行包含两个整数 $x$ 和 $y$，表示一个坏方硅片块的坐标（左上角的坐标为（$1,1$），左下角是 （$N,M$））。

输出格式

每行输出每个硅片最多可以从其切下的芯片数量。

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

提示

数据规模与约定

对于 $100 \%$ 的数据，$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$。

样例说明

题目说明

来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2002 的 Bugs Integrated,Inc.。
由 @求学的企鹅 翻译整理。