나일강을 끊지 마라 (라지)

외계인이 지구에 왔다. 고향 행성에는 흐르는 물이 아예 없어서 지구의 강을 신기하게 여기고, 이제 몇몇 강 위에 자기들 건물을 세우려고 한다. 당신이 맡은 일은 그 건물이 강의 흐름을 지나치게 막지 않는지 확인하는 것이다. 흐름이 막히면 큰 문제가 생긴다. 정확히는, 건물 배치가 주어졌을 때 강이 감당하는 최대 유량을 구해야 한다.

외계인은 곧게 뻗고 폭이 일정한 구간에 건물 세우기를 선호한다. 그래서 강을 직사각형 격자로 모형화한다. 각 칸은 정수 좌표 $(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 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$

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

아래 두 그림은 첫 번째 예제에 들어 있는 두 테스트 케이스를 그린 것이다.