Don't Break the Nile (Small)

Aliens have landed. Their home planet has no flowing water at all, so they find the rivers of Earth interesting and now want to put up their buildings inside some of them. Your job is to make sure the buildings do not block a river too badly, because that would cause serious trouble. Given the placement of the buildings, find the maximum flow the river can sustain.

The aliens build only on stretches of river that are straight and of uniform width, so you model a river as a rectangular grid. Each cell has integer coordinates $(X, Y)$ with $0 \le X < W$ and $0 \le Y < H$. Each cell sustains a flow of 1 unit through it, and water moves only between two cells that share an edge. Every cell on the south side of the river, that is every cell whose $y$ coordinate is $0$, receives an incoming flow of 1 from outside. Every building is a grid aligned rectangle, and a cell covered by a building sustains no flow at all. Under these rules, find the largest total flow that can reach the cells on the north side of the river, that is the cells whose $y$ coordinate is $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$. Here $(X_0, Y_0)$ is the lower left cell of the building and $(X_1, Y_1)$ is its upper right cell. Buildings never overlap, but two buildings may share an edge.

Limits

• $1 \le T \le 100$
• $3 \le W \le 100$
• $3 \le H \le 500$
• $0 \le B \le 10$
• $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 can pass through the river.

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