Bacteria - Problem

Problem

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):

If a bacterium has no neighbor to its north and no neighbor to its west, then it will die.
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.

Input

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₁ Y₁ X₂ Y₂. This indicates that all the cells with X coordinate between X₁ and X₂, inclusive, and Y coordinate between Y₁ and Y₂, 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.

Output

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.

Limits

Time limit: 30 5 seconds per test set.

Memory limit: 1GB.

1 ≤ C ≤ 100.

Small dataset (Test set 1 - Visible; 6 Points)

1 ≤ R ≤ 10

1 ≤ X₁ ≤ X₂ ≤ 100

1 ≤ Y₁ ≤ Y₂ ≤ 100

Large dataset (Test set 2 - Hidden; 25 Points)

1 ≤ R ≤ 1000

1 ≤ X₁ ≤ X₂ ≤ 1000000

1 ≤ Y₁ ≤ Y₂ ≤ 1000000

The number of cells initially containing bacteria will be at most 1000000.

Sample

Case #1: 6

QOJ.ac

QOJ