在无限的网格上分布着若干细菌，每个细菌占据一个独立的单元格。

每一秒钟，以下变换会同时发生：

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

输入包含：

• 一行包含 C，表示测试用例的数量。

对于每个测试用例：

• 一行包含 R，表示初始包含细菌的矩形区域数量。
• R 行，每行包含四个空格分隔的整数 X₁ Y₁ X₂ Y₂。这表示所有 X 坐标在 $X_1$ 到 $X_2$（含）之间，且 Y 坐标在 $Y_1$ 到 $Y_2$（含）之间的单元格都包含细菌。

矩形区域可能会重叠。

北侧是指 Y 坐标减小的方向。

西侧是指 X 坐标减小的方向。

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

样例

输入格式 1

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

输出格式 1

Case #1: 6