RECTNG1  Rectangles
There are n rectangles drawn on the plane. Each rectangle has sides parallel to the coordinate axes and integer coordinates of vertices.
We define a block as follows:
 each rectangle is a block,
 if two distinct blocks have a common segment then they form the new block otherwise we say that these blocks are separate.
Examples
The rectangles in Figure 1 form two separate blocks.
Figure 1
The rectangles in Figure 2 form a single block
Figure 2
Task
Write a program that for each test case:
 reads the number of rectangles and coordinates of their vertices;
 finds the number of separate blocks formed by the rectangles;
 writes the result to the standard output.
Input
The number of test cases t is in the first line of input, then t test cases follow separated by an empty line.
In the first line of a test case there is an integer n, 1 <= n <= 7000, which is the number of rectangles. In the following n lines there are coordinates of rectangles. Each rectangle is described by four numbers: coordinates x, y of the bottomleft vertex and coordinates x, y of the topright vertex. All these coordinates are nonnegative integers not greater than 10000.
Output
For each test case you should output one line with the number of separate blocks formed by the given rectangles.
Example
Sample input: 1 9 0 3 2 6 4 5 5 7 4 2 6 4 2 0 3 2 5 3 6 4 3 2 5 3 1 4 4 7 0 0 1 4 0 0 4 1 Sample output: 2
hide comments
:D:
20120503 10:47:03
O(N^2) can pass. 

Szabolcs Szucs:
20100409 22:35:49
what is the answer for these rectangles?:


Luke Pebody:
20100107 14:03:03
The answer seems to be 3? It seems that the pairs of rectangles that share segments are:

Added by:  MichaĆ Czuczman 
Date:  20040810 
Time limit:  1.279s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  5th Polish Olympiad in Informatics, stage 3 (Wojciech Rytter) 