Honeycomb Research

Albert studies honeycombs and honeybees as a hobby. As is well known, each cell of a honeycomb is hexagonal. For convenience, the honeycomb Albert studies is a hexagonal grid with $R$ rows and $C$ columns. The figure below shows the case $R = 5$, $C = 8$.

Albert wants to place tiny devices in some of the empty cells to observe honeybee behavior. A device occupies one cell, and each cell holds at most one device. Devices that are too close can interfere with each other. Specifically, a device does not interfere with the (at most) two neighboring cells in the same column, but it does interfere with the (at most) four neighboring cells in the other columns.

For example, suppose devices are placed at cells (1, 2), (2, 7), and (5, 6), as in the figure above.

• Cell (1, 2) has five neighbors. Devices cannot be placed at (1, 1), (2, 1), (1, 3), or (2, 3) because they may interfere. Cell (2, 2) is adjacent to (1, 2) but does not interfere with it.
• Cell (2, 7) has six neighbors. Cells (1, 6), (1, 8), (2, 6), and (2, 8) may interfere. Devices can still be added at (1, 7) and (3, 7).
• Cell (5, 6) has three neighbors. Cells (5, 5) and (5, 7) may interfere. A device can still be added at (4, 6).

With no other constraints, the most devices that avoid interference are placed in odd-numbered columns (1, 3, ...). Albert has proven that this is the maximum. However, Albert has two more concerns besides interference.

First, not every cell is empty. K cells contain cocoons instead of larvae, so no device can be placed there. The position of the i-th cell with a cocoon is $(X_i, Y_i)$.

Second, Albert wants to test a new sensor of the same size. The sensor also occupies one cell. It cannot be placed on a cocoon cell or on a cell that holds a device. The sensor interferes with every other device in its column. Cells in other columns do not interfere with it, even when adjacent. Only one sensor exists, and it must be installed.

For example, consider a grid with $R = 3$, $C = 3$, $K = 4$, $X = [1, 3, 1, 3]$, and $Y = [1, 1, 2, 3]$.

• In the second figure, the sensor is at (2, 2), and devices are at (2, 1), (1, 3), and (2, 3). This is possible.
• In the third figure, the sensor is at (2, 1), and devices are at (3, 2), (1, 3), and (2, 3). This is possible.
• In the rightmost figure, the sensor is at (2, 3), and devices are at (2, 2), (3, 2), and (1, 3). This layout fails because the sensor interferes with the device at (1, 3) in the same column. The device at (2, 2) is in a different column, so it does not interfere with the sensor.

In this example, the best result is 3 devices besides the sensor.

Another example uses $R = 3$, $C = 4$, $K = 6$, $X = [2, 1, 3, 1, 3, 3]$, and $Y = [1, 2, 2, 3, 3, 4]$.

• The middle figure places the sensor at (2, 2) and devices at (1, 1), (3, 1), (1, 4), and (2, 4). This is possible.
• The right figure places the sensor at (2, 3) and devices at (1, 1), (2, 2), (1, 4), and (2, 4). This is possible.

In this example, the best result is 4 devices besides the sensor. Other placements also reach 4.

Given $R$, $C$, $K$, $X$, and $Y$, find the maximum number of devices that can be installed while satisfying all the conditions above.

The first line contains the number of test cases $T$.

The first line of each test case contains $R$, $C$, and $K$, separated by spaces. If $K = 0$, the input for that test case ends on this line. If $K > 0$, the second line contains the $K$ integers of $X$ separated by spaces, and the third line contains the $K$ integers of $Y$ separated by spaces.

For each test case, print the answer on its own line.

• $1 \le T \le 5$
• $1 \le R, C \le 70$
• $0 \le K \le \min(500, R\cdot C - 1)$
• If $K > 0$, then for every $i$ with $1 \le i \le K$:
  • $1 \le X_i \le R$
  • $1 \le Y_i \le C$
  • The pairs $(X_i, Y_i)$ are distinct (no duplicate coordinates are given).