# Problem C

Sentry Robots

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 . . . . * . . . . * . .

## Input

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.

## Output

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 |
2 4 |