We need to guard a set of points of interest using sentry robots that can not move or turn. We can position a sentry at any position facing either north, south, east or west. Once a sentry is settled, it guards the points of interest that are infront of it. If two or more points are in the same row or column a single robot can guard them all. Unfortunately, there are also some obstacles that the robot cannot see through.
From a set of points of interest and obstacles lying on a grid, calculate the minimum number of robots needed to guard all the points. In order to guard a point of interest, a robot must be facing the direction of this point and must not be any obstacles in between.
Given the following grid, where # represents an obstacle and * a point of interest, the minimum number of robots needed is $2$ (a possible position and orientation is shown using arrows for each robot). Note that this is not the actual input or output, just a figure.
Grid Solution . . . . . . . . . . . . . * # * . . . * # * . . . . # . . . . . # . . . . * # * . . . ^ # ^ . .
For the following grid we need $4$ robots because of the obstacles.
Grid Solution . * * . . . > * . . . * # * . . ^ # ^ . . # * . . . # v . . . . * . . . . * . .
The first line of the input has an integer $C$ ($1 \leq C \leq 50$) representing the number of test cases that follow.
Before each test case there is an empty line. For each case, the first line has 2 integers, $Y$ and $X$ ($1 \leq Y, X \leq 100$), representing the height and width of the grid. The next line has an integer that indicates the number of points of interest $P$. The following $P$ lines will have the positions $p_ y$ and $p_ x$ of the points of interest, one point per line ($1 \leq p_ y \leq Y$, $1 \leq p_ x \leq X$). The next line has an integer that indicates the number of obstacles $W$. The following $W$ lines will have the positions $w_ y$ and $w_ x$ of an obstacle, one per line ($1 \leq w_ y \leq Y$, $1 \leq w_ x \leq X$). It holds that $0 \leq P + W \leq Y \cdot X$, and that all positions are different.
For each test case print the minimum number of robots needed to guard all the points of interest, one per line.
|Sample Input 1||Sample Output 1|
2 4 6 4 2 2 2 4 4 2 4 4 3 2 3 3 3 4 3 4 5 6 1 2 1 3 2 4 2 2 3 3 4 3 2 2 3 3 2