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.

The rectangles in Figure 2 form a single block

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 bottom-left vertex and coordinates x, y of the top-right vertex. All these coordinates are non-negative 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

Added by:Michał Czuczman
Date:2004-08-10
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)

hide comments
2012-05-03 10:47:03 :D
O(N^2) can pass.
2010-04-09 22:35:49 Szabolcs Szucs
what is the answer for these rectangles?:

2
0 0 3 3
1 1 2 2

Last edit: 2010-04-13 12:44:52
2010-01-07 14:03:03 Luke Pebody
The answer seems to be 3? It seems that the pairs of rectangles that share segments are:
rectangle 1 with rectangle 8
rectangle 2 with rectangle 7
rectangle 3 with rectangles 5 and 6
rectangle 4 with rectangle 9
rectangle 8 with rectangle 9
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.