Bacteria (Large)

Time limit5sMemory limit512 MB

Summary

Given initially filled rectangles on a grid evolving by a north-west neighbor rule, compute the seconds until no bacterium remains.

Level: Medium7 of 10
Topics: Dynamic programming, Simulation, Matrix
Solved: No attempts yet

Problem

Bacteria live on an infinite grid of cells, and each bacterium occupies one cell.

Every second all of the following changes happen at the same time.

A bacterium with no neighbor to its north and no neighbor to its west dies.
An empty cell whose north neighbor and west neighbor both hold a bacterium gains a new bacterium.

When you look at the grid, the number of bacteria is finite and at least one, and the occupied cells form one or more rectangular regions. Compute how many seconds pass before every bacterium is dead.

The grid below starts with 6 bacteria and is empty after 6 seconds. A 1 is a cell with a bacterium and a 0 is an empty cell. The pictures are one second apart.

Input

The first line has $C$ , the number of test cases. Each test case is given in this form.

One line with $R$ , the number of rectangular regions that initially contain bacteria.
$R$ lines with four space separated integers $X_1$ $Y_1$ $X_2$ $Y_2$ . Every cell whose X coordinate is between $X_1$ and $X_2$ inclusive and whose Y coordinate is between $Y_1$ and $Y_2$ inclusive contains a bacterium.

The rectangles may overlap.

North is the direction of decreasing Y coordinate. West is the direction of decreasing X coordinate.

Limits

$1 \le C \le 25$
$1 \le R \le 1000$
$1 \le X_1 \le X_2 \le 500$
$1 \le Y_1 \le Y_2 \le 500$

Output

For each test case print one line of the form Case #N: T, where $N$ is the test case number counted from 1 and $T$ is the number of seconds until every bacterium is dead.

Examples2

Example 1
Input
```
1
3
5 1 5 1
2 2 4 2
2 3 2 4
```
Expected output
```
Case #1: 6
```
Example 2
Input
```
1
1
1 1 1 1
```
Expected output
```
Case #1: 1
```