题目描述

Bugs Integrated，Inc是高级存储芯片的主要制造商。

他们正在生产一种新的6TB Q-RAM芯片。

每个芯片由六个单位方块组成，以$\red {2 \times 3}$矩形的形式排列。

该公司通过分割$\red {N \times M}$个单位方块组成的矩形硅片得到多个Q-RAM芯片。

大的矩形硅片会被完整检测，并且其中坏掉的方块会用黑色标明。

矩形硅片要被分割成尽可能多的芯片，并且每个芯片中都不能包含坏掉的方块，请你求出最优解法。

输入格式

第一行包含整数$\red {D}$，表示共有$\red {D}$组测试数据。

每组测试数据第一行包含三个整数$\red {N}$,$\red {M}$和$\red {K}$，其中$\red {K}$为坏掉的方块数量。

接下来$\red {K}$行，每行包含两个整数$\red {x}$，$\red {y}$，表示一个坏掉的方块的位置坐标$\red {(x,y)}$。（矩形硅片的左上角坐标为$\red {(1,1)}$,右下角坐标为$\red {(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

提示

$\red {1≤D≤5}$，

$\red {1≤N≤150}$,

$\red {1≤M≤10}$,

$\red {1≤K≤NM}$,