描述

集成漏洞公司（Bugs Integrated, Inc.）是先进内存芯片的主要制造商。他们正在启动新型六太字节Q-RAM芯片的生产。每个芯片由六个单位正方形组成，排列成一个\(2\times3\)的矩形。制造Q-RAM芯片的方式是：取一块被划分为\(N\times M\)个单位正方形的硅片。然后仔细测试所有正方形，用黑色记号笔标记出有问题的正方形。

最后，将硅片切割成内存芯片。每个芯片由\(2\times3\)（或\(3\times2\)）个单位正方形组成。当然，任何芯片都不能包含有问题（已标记）的正方形。可能无法将硅片切割成使得每个好的单位正方形都成为某个内存芯片的一部分。公司希望尽可能少地浪费好的正方形。因此，他们想知道如何切割硅片以得到尽可能多的芯片。

任务

你会得到若干个硅片的尺寸以及每个硅片上所有有问题的单位正方形的列表。你的任务是编写一个程序，对于每个硅片，计算出从该硅片上能够切割出的最大芯片数量。

输入

输入文件的第一行包含一个整数\(D\)（\(1\leq D\leq 5\)），表示硅片的数量。接下来是\(D\)个数据块，每个数据块描述一个硅片。每个数据块的第一行包含三个整数\(N\)（\(1\leq N\leq 150\)）、\(M\)（\(1\leq M\leq 10\)）、\(K\)（\(0\leq K\leq MN\)），它们之间用单个空格分隔。\(N\)是硅片的长度，\(M\)是硅片的高度，\(K\)是硅片上有问题的正方形的数量。接下来的\(K\)行包含有问题的正方形的列表。每行包含两个整数\(x\)和\(y\)（\(1\leq x\leq N\)，\(1\leq y\leq M\)），表示一个有问题的正方形的坐标（左上角的正方形坐标为\([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

来源

2002年中欧信息学奥林匹克竞赛（CEOI 2002）