Description

有若干细菌分布在一个无限大的网格上，每个细菌占据一个单独的格子。

每一秒，所有细菌会同时发生如下变化：

1. 如果某个细菌的北侧和西侧都没有邻居细菌，则该细菌会死亡。
2. 如果某个格子没有细菌，但其北侧和西侧的格子都有细菌，则该格子会诞生一个新的细菌。

你观察到，网格上有若干个矩形区域，每个区域内有若干个细菌，且细菌的总数为正且有限。

请你计算，经过多少秒后，所有细菌都会死亡。

下面是一个初始有 6 个细菌的网格示例，全部细菌死亡共需 6 秒。'1' 表示有细菌的格子，'0' 表示无细菌的格子。

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

Input Format

输入包含：

• 第一行一个整数 $C$，表示测试用例的数量。

接下来每个测试用例包含：

• 一行一个整数 $R$，表示初始含有细菌的矩形区域数量。
• 接下来 $R$ 行，每行四个用空格分隔的整数 $X_1$ $Y_1$ $X_2$ $Y_2$，表示 $X_1 \leq X \leq X_2$ 且 $Y_1 \leq Y \leq Y_2$ 的所有格子内都有细菌。

这些矩形区域可能重叠。

北侧指 $Y$ 坐标减小的方向，西侧指 $X$ 坐标减小的方向。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$N$: $T$"，其中 $N$ 表示测试用例编号（从 1 开始），$T$ 表示所有细菌全部死亡所需的秒数。

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

Case #1: 6

Hint

数据范围

• $1 \leq C \leq 100$

小数据（6 分，测试点 1 - 可见）

• $1 \leq R \leq 10$
• $1 \leq X_1 \leq X_2 \leq 100$
• $1 \leq Y_1 \leq Y_2 \leq 100$

大数据（25 分，测试点 2 - 隐藏）

• $1 \leq R \leq 1000$
• $1 \leq X_1 \leq X_2 \leq 1000000$
• $1 \leq Y_1 \leq Y_2 \leq 1000000$
• 初始含有细菌的格子总数不超过 $1000000$。

由 ChatGPT 4.1 翻译