나일강을 막지 마라 (Small)

외계인이 지구에 내려왔다. 이들의 고향 행성에는 흐르는 물이 전혀 없어서 외계인은 지구의 강을 신기하게 여기고, 몇몇 강 안에 자기들의 건물을 세우려고 한다. 당신이 맡은 일은 이 건물이 강물의 흐름을 지나치게 막지 않는지 확인하는 것이다. 흐름이 막히면 심각한 문제가 생긴다. 건물 배치가 주어졌을 때 강이 감당할 수 있는 최대 유량을 구하라.

외계인은 곧게 뻗어 있고 폭이 일정한 구간에만 건물을 세우려고 한다. 그래서 강을 직사각형 격자로 나타낸다. 각 칸의 좌표는 정수 $(X, Y)$이며 $0 \le X < W$, $0 \le Y < H$를 만족한다. 각 칸은 1만큼의 유량을 감당하고, 물은 변을 맞댄 두 칸 사이로만 흐른다. 강의 남쪽 경계에 있는 칸, 즉 $y$좌표가 $0$인 모든 칸에는 바깥에서 1만큼의 물이 들어온다. 건물은 모두 격자에 맞춰 놓인 직사각형이고, 건물이 덮은 칸은 물을 전혀 흘려보내지 못한다. 이 조건에서 강의 북쪽 경계, 즉 $y$좌표가 $H - 1$인 칸까지 도달할 수 있는 최대 유량을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 강의 폭 $W$, 강의 높이 $H$, 강에 놓인 건물의 개수 $B$가 정수로 주어진다. 다음 $B$개의 줄에는 각각 네 정수 $X_0$, $Y_0$, $X_1$, $Y_1$이 주어진다. $(X_0, Y_0)$은 건물의 왼쪽 아래 칸의 좌표이고, $(X_1, Y_1)$은 오른쪽 위 칸의 좌표이다. 건물끼리 겹치지는 않지만 변을 맞댈 수는 있다.

제한

• $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$

각 테스트 케이스마다 Case #x: m 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $m$은 강을 통과할 수 있는 최대 유량이다.

아래 두 그림은 예제 입력의 두 테스트 케이스를 그린 것이다.