Rectangles Too!

Time limit3sMemory limit128 MB

Summary

Find the longest chain of rectangles where each rectangle lies strictly below and to the left of the next one.

Level: Hard8 of 10
Topics: Sorting, Dynamic programming, Segment tree
Solved: No attempts yet

Problem

A rectangle in the Cartesian plane is given by two corner points $(x_1, y_1)$ and $(x_2, y_2)$ , its lower-left and upper-right corners, with $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$ , when

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

You are given a collection of rectangles in the plane. Find the length $L$ of the longest sequence of rectangles $(A_1, A_2, \ldots, A_L)$ from the collection such that

$A_1 \preceq A_2 \preceq \cdots \preceq A_L.$

Input

The input contains several test cases. Each test case starts with a line containing one integer $n$ ( $1 \le n \le 100000$ ), the number of rectangles. Each of the next $n$ lines contains four integers $x_1\ y_1\ x_2\ y_2$ ( $-1000000 \le x_1 \le x_2 \le 1000000$ and $-1000000 \le y_1 \le y_2 \le 1000000$ ), the lower-left and upper-right corners of one rectangle. The input ends with a line containing a single $0$ .

Output

For each test case, print one line with a single integer: the length of the longest chain of rectangles.

Examples2

Example 1

Input

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

Expected output

2
1

Example 2
Input
```
1
0 0 1 1
0
```
Expected output
```
1
```