题目描述

臭虫集成电路公司是我国先端内存芯片的主要供应厂商。他们新投产了一种 6TB 的 Q-RAM 芯片，每块这种芯片可以表示为 $2 \times 3$ 的矩形。 Q-RAM 芯片是从一块 $N \times M$ 的硅片上切下来的，但由于臭虫王国的半导体技术不够发达，产品的原料经常不够纯，因而有若干的单位正方形并不能作为芯片的一部分。

臭虫集成电路公司想要知道，给定一块 $N \times M$ 大小的硅片和原料不纯的单位正方形的位置，最多能使用这块硅片生产多少 Q-RAM 芯片。

输入格式

输入的第一行由一个正整数 $D$ 构成，表示硅片的个数。

随后跟着 $D$ 个数据，每个数据第一行包含三个整数 $N,$ $M,$ $K$，分别表示硅片的长和宽，以及硅片原料不纯的单位正方形个数。接下 $K$ 行，每行两个整数 $X,$ $Y$ ，表示单位正方形的坐标。（左上角的单位正方形用 $(1,1)$ 表示，右下角的单位正方形用 $(N,M)$ 表示。）

输出格式

共 $D$ 行，每行一个整数，即最多能切出多少个 Q-RAM 芯片。

样例

input

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

output

3
4

数据范围与提示

共有 $10$ 个测试点，测试点间独立计分。

对于 $10 \%$ 的数据（测试点 #10），有 $K = 0$；
对于另 $10 \%$ 的数据（测试点 #4），有 $D = 1, \ K = 1$；
对于另 $10 \%$ 的数据（测试点 #1），有 $K \leq 1$；
对于所有数据，$ 1 \leq D \leq 5 $，$ 1 \leq N \leq 150 $，$ 1 \leq M \leq 10 $，$ 0 \leq K \leq MN $。

请注意内存和时间限制。