Người ngoài hành tinh đã đổ bộ. Những người ngoài hành tinh này thấy các con sông trên Trái Đất rất thú vị vì hành tinh quê hương của họ hoàn toàn không có nước chảy, và giờ họ muốn xây dựng các công trình của mình ở một số con sông trên Trái Đất. Bạn được giao nhiệm vụ đảm bảo rằng các tòa nhà của họ không cản trở dòng chảy của những con sông này quá nhiều, điều này có thể gây ra các vấn đề nghiêm trọng. Cụ thể, bạn cần xác định lưu lượng dòng chảy tối đa mà con sông có thể duy trì là bao nhiêu, dựa trên vị trí của các tòa nhà.

Người ngoài hành tinh thích xây dựng các tòa nhà của họ trên những đoạn sông thẳng và có chiều rộng đồng nhất. Do đó, bạn quyết định mô hình hóa con sông dưới dạng một lưới hình chữ nhật, trong đó mỗi ô có tọa độ nguyên (\(X, Y\); \(0 \le X < W\) và \(0 \le Y < H\)). Mỗi ô có thể duy trì một dòng chảy là \(1\) đơn vị đi qua nó, và nước có thể chảy giữa các ô kề cạnh. Tất cả các ô ở phía nam của con sông (tức là có tọa độ \(y\) bằng \(0\)) có một dòng chảy ngầm đi vào là \(1\). Tất cả các tòa nhà đều có hình chữ nhật và căn chỉnh theo lưới. Các ô nằm dưới một tòa nhà không thể duy trì bất kỳ dòng chảy nào. Với các ràng buộc này, hãy xác định lượng dòng chảy tối đa có thể đến được các ô ở phía bắc của con sông (tức là có tọa độ \(y\) bằng \(H-1\)).

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm sẽ bắt đầu bằng một dòng duy nhất chứa ba số nguyên, \(W\), chiều rộng của con sông, \(H\), chiều cao của con sông, và \(B\), số lượng tòa nhà được đặt trong sông. \(B\) dòng tiếp theo sẽ mỗi dòng chứa bốn số nguyên, \(X0, Y0, X1,\) và \(Y1\). \(X0, Y0\) là tọa độ của góc dưới bên trái của tòa nhà, và \(X1, Y1\) là tọa độ của góc trên bên phải của tòa nhà. Các tòa nhà sẽ không chồng lấn lên nhau, mặc dù hai tòa nhà có thể chung cạnh.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: m", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và m là lưu lượng tối đa có thể đi qua sông.

Ràng buộc

• \(1 \le T \le 100\).
• \(0 \le X0 \le X1 < W\).
• \(0 \le Y0 \le Y1 < H\).

Phân nhóm

• Small dataset:

  • \(3 \le W \le 100\).
  • \(3 \le H \le 500\).
  • \(0 \le B \le 10\).

  • Large dataset:

  • \(3 \le W \le 1000\).

  • \(3 \le H \le 10^8\).
  • \(0 \le B \le 1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

Ví dụ 1

Input

2
3 3 2
2 0 2 0
0 2 0 2
5 6 4
1 0 1 0
3 1 3 3
0 2 1 3
1 5 2 5

Output

Case #1: 1
Case #2: 2

Note

Dưới đây là hình ảnh minh họa cho hai bộ thử nghiệm trong ví dụ:

Nguồn

Google Code Jam 2014, Vòng 2, bài Don't Break The Nile.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.