시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 4 3 3 75.000%

## 문제

A rectangle in the Cartesian plane is specified by a pair of coordinates ($x_1$, $y_1$) and ($x_2$, $y_2$) indicating its lower-left and upper-right corners, respectively (where $x_1$ ≤ $x_2$ and $y_1$ ≤ $y_2$). Given a pair of 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 write $A$ ⪯ $B$ (i.e., $A$ "precedes" $B$), if

$x_2^A$ < $x_1^B$ and $y_2^A$ < $y_1^B$.

In this problem, you are given a collection of rectangles located in the two-dimension Euclidean plane. Find the length L of the longest sequence of rectangles ($A_1$, $A_2$, ..., $A_L$) from this collection such that

$A_1$ ⪯ $A_2$ ⪯ ... ⪯ $A_L$.

## 입력

The input file will contain multiple test cases. Each test case will begin with a line containing a single integer $n$ (where 1 ≤ $n$ ≤ 100000), indicating the number of input rectangles. The next $n$ lines each contain four integers $x_1^i$ $y_1^i$ $x_2^i$ $y_2^i$ (where −1000000 ≤ $x_1^i$ ≤ $x_2^i$ ≤ 1000000, −1000000 ≤ $y_1^i$ ≤ $y_2^i$ ≤ 1000000, and 1 ≤ $i$ ≤ $n$), indicating the lower left and upper right corners of a rectangle. The end-of-file is denoted by a single line containing the integer 0.

## 출력

For each input test case, print a single integer indicating the length of the longest chain.

## 예제 입력 1

3
1 5 2 8
3 -1 5 4
10 10 20 20
2
2 1 4 5
6 5 8 10
0


## 예제 출력 1

2
1