Don't Break the Nile (Large)

Aliens have landed. Their home planet has no flowing water at all, so they find the rivers of Earth interesting, and now they want to put up their buildings in some of those rivers. Your job is to check that the buildings do not block the rivers too much, because a blocked river causes serious trouble. Given the placement of the buildings, determine the maximum flow the river sustains.

The aliens prefer stretches of river that are straight and of uniform width, so you model the river as a rectangular grid. Each cell has integer coordinates $(X, Y)$ with $0 \le X < W$ and $0 \le Y < H$. Each cell passes 1 unit of flow, and water moves between two cells that share an edge. Every cell on the south side of the river, meaning every cell with $y$ coordinate $0$, receives 1 unit of incoming flow. All buildings are rectangles aligned with the grid, and a cell under a building passes no flow at all.

Under these rules, determine the maximum flow that reaches the north side of the river, meaning the cells with $y$ coordinate $H-1$.

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

The first line of each test case contains three integers: the width of the river $W$, the height of the river $H$, and the number of buildings placed in the river $B$. Each of the next $B$ lines contains four integers $X_0$, $Y_0$, $X_1$, $Y_1$. $(X_0, Y_0)$ is the lower left corner of the building and $(X_1, Y_1)$ is the upper right corner. Buildings do not overlap, although two buildings can share an edge.

Limits

• $1 \le T \le 100$
• $3 \le W \le 1000$
• $3 \le H \le 10^8$
• $0 \le B \le 1000$
• $0 \le X_0 \le X_1 < W$
• $0 \le Y_0 \le Y_1 < H$

For each test case, print one line in the form Case #x: m, where $x$ is the test case number starting from 1 and $m$ is the maximum flow that passes through the river.

The two pictures below draw the two test cases of the first example.