Một căn phòng lớn chứa đầy các bẫy chuột được sắp xếp theo dạng lưới. Mỗi bẫy chuột được nạp hai quả bóng bàn, được đặt cẩn thận sao cho khi bẫy chuột sập, chúng sẽ được bắn ra, rơi trúng các bẫy chuột khác và kích hoạt chúng. Các bức tường của căn phòng có tính chất dính, vì vậy bất kỳ quả bóng nào đập vào tường đều bị hấp thụ.

Mỗi bẫy chuột khi bị trúng bóng sẽ bắn hai quả bóng bàn theo cùng một cách: chuyển động của chúng được xác định bởi một độ dời X và Y so với bẫy chuột xuất phát. Sau đó, bạn quyết định ném một quả bóng bàn duy nhất vào phòng. Nó trúng một bẫy chuột, kích hoạt bẫy đó và bắn ra hai quả bóng của nó. Hai quả bóng này sau đó kích hoạt thêm hai bẫy chuột nữa, và giờ có bốn quả bóng bay ra... Khi bụi lắng xuống, nhiều bẫy chuột đã bị kích hoạt, nhưng một số bẫy đã bị bỏ lỡ bởi tất cả các quả bóng đang bay.

Bạn cần tính xem có bao nhiêu bẫy chuột sẽ bị kích hoạt.

Ví dụ (xem ví dụ mẫu đầu tiên), hình ảnh dưới đây minh họa một căn phòng có chiều rộng 5, chiều cao 3. Hai hướng của các quả bóng bàn trong mỗi phòng lần lượt là (-1, 0) và (-1, -1). Quả bóng đầu tiên bạn ném trúng bẫy chuột ở vị trí (4, 2). Cuối cùng, 12 bẫy chuột được kích hoạt.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, C. C bộ test tiếp theo. Mỗi bộ test chứa bốn dòng. Dòng đầu tiên là kích thước của lưới bẫy chuột (bằng kích thước của căn phòng), được cho bởi chiều rộng W và chiều cao H. Hai dòng tiếp theo cho biết điểm đến của hai quả bóng bàn, dưới dạng độ dời X và Y. Ví dụ, nếu hai dòng là 0 1 và 1 1, thì việc kích hoạt một bẫy chuột sẽ bắn ra hai quả bóng; một quả sẽ trúng bẫy chuột ngay phía trên bẫy bị kích hoạt, và quả kia sẽ trúng bẫy chuột ở phía trên và bên phải của bẫy bị kích hoạt. Dòng cuối cùng có hai số nguyên xác định tương ứng cột và hàng của bẫy chuột bị quả bóng bàn ban đầu kích hoạt (trong đó 0 0 là bẫy chuột ở góc dưới bên trái).

Dữ liệu ra

Đối với mỗi bộ test, hãy in ra một dòng chứa "Case #A: B", trong đó A là số thứ tự của bộ test (bắt đầu từ 1) và B là số lượng bẫy chuột bị kích hoạt (bao gồm cả bẫy đầu tiên).

Ràng buộc

• 1 ≤ C ≤ 100
• -20 ≤ bất kỳ độ dời nào ≤ 20
• Không có vector nào có độ dài bằng 0.

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1): 2 ≤ W, H ≤ 100
• Tập dữ liệu lớn (Test set 2): 2 ≤ W, H ≤ 1000000

Đ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ụ

3
5 3
-1 0
-1 -1
4 2
50 50
0 1
1 1
10 10
6 2
2 0
3 0
0 0

Case #1: 12
Case #2: 820
Case #3: 5

Nguồn

Google Code Jam 2008, Chung kết thế giới, bài Ping Pong Balls.

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