题目描述

A number of bacteria lie on an infinite grid of cells, each bacterium in its own cell.

Each second, the following transformations occur (all simultaneously):

1. If a bacterium has no neighbor to its north and no neighbor to its west, then it will die.
2. If a cell has no bacterium in it, but there are bacteria in the neighboring cells to the north and to the west, then a new bacterium will be born in that cell.

Upon examining the grid, you note that there are a positive, finite number of bacteria in one or more rectangular regions of cells.

Determine how many seconds will pass before all the bacteria die.

Here is an example of a grid that starts with 6 cells containing bacteria, and takes 6 seconds for all the bacteria to die. '1's represent cells with bacteria, and '0's represent cells without bacteria.

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

输入格式

The input consists of:

• One line containing $C$, the number of test cases.

Then for each test case:

• One line containing $R$, the number of rectangles of cells that initially contain bacteria.
• $R$ lines containing four space-separated integers $X_1$ $Y_1$ $X_2$ $Y_2$. This indicates that all the cells with X coordinate between $X_1$ and $X_2$, inclusive, and Y coordinate between $Y_1$ and $Y_2$, inclusive, contain bacteria.

The rectangles may overlap.

North is in the direction of decreasing Y coordinate.

West is in the direction of decreasing X coordinate.

输出格式

For each test case, output one line containing "Case #$N$: $T$", where $N$ is the case number (starting from 1), and $T$ is the number of seconds until the bacteria all die.

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

Case #1: 6

提示

Limits

• $1 \leq C \leq 100.$

Small dataset (6 Pts, Test set 1 - Visible)

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

Large dataset (25 Pts, Test set 2 - Hidden)

• $1 \leq R \leq 1000$
• $1 \leq X_1 \leq X_2 \leq 1000000$
• $1 \leq Y_1 \leq Y_2 \leq 1000000$
• The number of cells initially containing bacteria will be at most $1000000$.