Long live the Bacteria

All submissions for this problem are available.
Amogh has a huge collection of bacteria for some research (probably for his database :P). He lays them on an infinite grid of cells, each bacterium in its own cell.
Now, these bacterium are special, as they reproduce or die following a unique pattern.
He observes that 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, he notes that there are a positive, finite number of bacteria in one or more rectangular regions of cells.
Now, he wants to calculate the number of seconds that will pass before all the bacteria die.
Can you help him with that?
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
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 spaceseparated integers X1 Y1 X2 Y2. This indicates that all the cells with X coordinate between X1 and X2, inclusive, and Y coordinate between Y1 and Y2, 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 T, where T is the number of seconds until all the bacteria die.
Constraints
Should contain all the constraints on the input data that you may have. Format it like:
 1 ≤ C ≤ 100
 1 ≤ R ≤ 1000
 1 ≤ X1 ≤ X2≤1000000
 1 ≤ Y1 ≤ Y2≤1000000
 The number of cells initially containing bacteria will be at most 1000000.
Example
Input: 1 3 5 1 5 1 2 2 4 2 2 3 2 4 Output: 6
Author:  prongs7 
Tags  prongs7 
Date Added:  25092014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 