시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB303375.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