Một số vi khuẩn nằm trên một lưới ô vuông vô hạn, mỗi vi khuẩn nằm trong một ô riêng biệt.

Mỗi giây, các biến đổi sau đây sẽ xảy ra (tất cả đồng thời):

1. Nếu một vi khuẩn không có láng giềng ở phía bắc và không có láng giềng ở phía tây, nó sẽ chết.
2. Nếu một ô không có vi khuẩn, nhưng có vi khuẩn ở các ô láng giềng phía bắc và phía tây, thì một vi khuẩn mới sẽ được sinh ra ở ô đó.

Sau khi kiểm tra lưới, bạn nhận thấy có một số lượng vi khuẩn hữu hạn và dương nằm trong một hoặc nhiều vùng hình chữ nhật.

Hãy xác định xem sau bao nhiêu giây thì tất cả vi khuẩn sẽ chết.

Dưới đây là một ví dụ về lưới bắt đầu với 6 ô chứa vi khuẩn và mất 6 giây để tất cả vi khuẩn chết. Số '1' đại diện cho ô có vi khuẩn, và số '0' đại diện cho ô không có vi khuẩn.

000010
011100
010000
010000
000000

000000
001110
011000
010000
000000

000000
000110
001100
011000
000000

000000
000010
000110
001100
000000

000000
000000
000010
000110
000000

000000
000000
000000
000010
000000

000000
000000
000000
000000
000000

Dữ liệu vào

• Một dòng chứa số nguyên \(C\), số lượng bộ thử nghiệm (test case).
  Tiếp theo là các bộ thử nghiệm, mỗi bộ gồm:
• Một dòng chứa số nguyên \(R\), số lượng hình chữ nhật chứa vi khuẩn ban đầu.
• \(R\) dòng, mỗi dòng chứa bốn số nguyên cách nhau bởi dấu cách \(X_1, Y_1, X_2, Y_2\). Điều này cho biết tất cả các ô có tọa độ \(X\) từ \(X_1\) đến \(X_2\) (bao gồm cả hai đầu) và tọa độ \(Y\) từ \(Y_1\) đến \(Y_2\) (bao gồm cả hai đầu) đều chứa vi khuẩn.

Các hình chữ nhật có thể chồng lấp lên nhau.

Phía Bắc là hướng có tọa độ \(Y\) giảm dần.
Phía Tây là hướng có tọa độ \(X\) giảm dần.

Dữ liệu ra

Với mỗi bộ thử nghiệm, in ra một dòng chứa "Case #N: T", trong đó N là số thứ tự bộ thử nghiệm (bắt đầu từ 1), và T là số giây cho đến khi tất cả vi khuẩn chết hết.

Ràng buộc

• \(1 \le C \le 100\).

Phân nhóm

• Thông thường (Test set 1):
  • \(1 \le R \le 10\)
  • \(1 \le X_1 \le X_2 \le 100\)
  • \(1 \le Y_1 \le Y_2 \le 100\)
• Lớn (Test set 2):
  • \(1 \le R \le 1000\)
  • \(1 \le X_1 \le X_2 \le 1,000,000\)
  • \(1 \le Y_1 \le Y_2 \le 1,000,000\)
  • Số lượng ô ban đầu chứa vi khuẩn tối đa là \(1,000,000\).

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

1
3
5 1 5 1
2 2 4 2
2 3 2 4

Case #1: 6

Nguồn

Google Code Jam 2010, Vòng 2, bài Bacteria.

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