Rectangles

A rectangle in the coordinate plane is given by a pair of corner coordinates: its lower-left corner $(x_1, y_1)$ and its upper-right corner $(x_2, y_2)$, where $x_1 \le x_2$ and $y_1 \le y_2$.

For two rectangles $A = ((x_1^A, y_1^A), (x_2^A, y_2^A))$ and $B = ((x_1^B, y_1^B), (x_2^B, y_2^B))$, we say that $A$ precedes $B$, written $A \preceq B$, if

$x_2^A < x_1^B \quad \text{and} \quad y_2^A < y_1^B.$

In other words, the upper-right corner of $A$ must be strictly smaller than the lower-left corner of $B$ in both coordinates.

Given a collection of rectangles, find the length $L$ of the longest sequence of rectangles $(A_1, A_2, \dots, A_L)$ such that

$A_1 \preceq A_2 \preceq \dots \preceq A_L.$

The input consists of several test cases. Each test case begins with a line containing a single integer $n$ $(1 \le n \le 1000)$, the number of rectangles. Each of the next $n$ lines contains four integers $x_1^i\ y_1^i\ x_2^i\ y_2^i$, giving the lower-left and upper-right corners of the $i$-th rectangle, where $-1000000 \le x_1^i \le x_2^i \le 1000000$ and $-1000000 \le y_1^i \le y_2^i \le 1000000$.

The end of input is indicated by a line containing a single $0$.

For each test case, print the length of the longest chain as a single integer on its own line.