Description
There are some rectangles in 2 dimensional space. We define some relations:
(1) Intersect: Choose any 2 rectangles A and B. They intersect each other if and only if there exists at least one point that can cover by the 2 rectangles. If A and B intersect, they are in the same group.
Figure 1. Sample of intersection
(2) Transitivity: Choose any 3 rectangles A, B, C. If A intersect B and B intersect C, we denote that A, B, C are in the same group.
Figure 2. Sample of Transitivity
Given the rectangles in the 2D space, please find the size of the maximum rectangle group.
Input
There are more than one cases in the input. Each case contains N rectangles in the first line of the case. In the next n lines, each line contains 4 integers: lx, ly, rx, ry. (0 <= lx, ly, rx, ry <= 1000)
lx, ly denote the left-bottom coordinate of the rectangle.
rx, ry denote the right-top coordinate of the rectangle.
Input ends with N = 0.
9212 O(N!*N) can pass this input, N <= 10
9213 O(N3) can pass this input, N <= 100
9214 O(N2) can pass this input, N <= 1000
9215 O(N2) can pass this input, N <= 1000
Output
For each test case, output the number of maximum group in one line.
Take first input for examples.
