나일강을 막지 마라

외계인들이 착륙했다. 이 외계인들은 자신들의 고향 행성에는 흐르는 물이 전혀 없기 때문에 지구의 강을 흥미롭게 여기며, 이제 지구의 몇몇 강에 외계 건물을 건설하려 한다. 여러분은 그 건물들이 강의 흐름을 지나치게 방해하여 심각한 문제를 일으키지 않도록 해야 한다. 구체적으로, 건물의 배치가 주어졌을 때 강이 감당할 수 있는 최대 유량을 구해야 한다.

외계인들은 곧고 폭이 일정한 강 구간에 건물을 짓는 것을 선호한다. 따라서 강을 직사각형 격자로 모델링하기로 한다. 각 칸은 정수 좌표 (X, Y; 0 ≤ X < W 및 0 ≤ Y < H)를 갖는다. 각 칸은 그 칸을 통과하는 1 단위의 유량을 감당할 수 있으며, 물은 변을 공유하는 칸 사이로 흐를 수 있다. 강의 남쪽에 있는 모든 칸(즉, y좌표가 0인 칸)에는 1의 유입량이 암묵적으로 주어진다. 모든 건물은 직사각형이며 격자에 맞춰져 있다. 건물 아래에 놓인 칸은 어떠한 유량도 감당할 수 없다. 이 제약 조건에서 강의 북쪽에 있는 칸(즉, y좌표가 H-1인 칸)에 도달할 수 있는 최대 유량을 구한다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 0 ≤ X0 ≤ X1 < W. 0 ≤ Y0 ≤ Y1 < H.

작은 데이터 세트

시간 제한: 60초. 3 ≤ W ≤ 100. 3 ≤ H ≤ 500. 0 ≤ B ≤ 10.

큰 데이터 세트

시간 제한: 120초. 3 ≤ W ≤ 1000. 3 ≤ H ≤ $10^{8}$. 0 ≤ B ≤ 1000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 정수 W, H, B가 포함된 한 줄로 시작한다. W는 강의 너비, H는 강의 높이, B는 강에 배치되는 건물의 수이다. 다음 B개의 줄에는 각각 네 정수 X0, Y0, X1, Y1가 주어진다. X0, Y0는 건물의 왼쪽 아래 모서리 좌표이고, X1, Y1는 건물의 오른쪽 위 모서리 좌표이다. 두 건물이 한 변을 공유할 수는 있지만, 건물끼리 겹치지는 않는다.

각 테스트 케이스마다 "Case #x: m"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, m은 강을 통과할 수 있는 최대 유량이다.

다음은 예제 입력에 있는 두 테스트 케이스를 시각적으로 나타낸 것이다: