Migrated from Lutece 614 The Longest Sequence of Rectangles

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A rectangle is specified by a pair of coordinates $(x_1 , y_1)$ and $(x_2 , y_2)$ indicating its lower-left and upper-right corners ($x_1 \leq x_2$ and $y_1 \leq y_2$). For a pair of rectangles, $A = ((X_{A_1}, Y_{A_1}), (X_{A_2}, Y_{A_2}))$ and $B = ((X_{B_1}, Y_{B_1}), (X_{B_2}, Y_{B_2}))$, we define $A \leq B$ if $X_{A_2}<X_{B_1}$ and $Y_{A_2}<Y_{B_1}$. Given a number of rectangles on the plane, you are asked to find the length $L$ of the longest sequence of rectangles $(A_1, A_2, \cdots, A_L)$ such that $A_1 \leq A_2 \leq \cdots \leq A_L$.

Input

The input contains multiple test cases. The first line of the input is an integer $T$, indicating the number of test cases. Each test case begins with a line containing a single integer $n$ ($1 \leq n \leq 100000$), indicating the number of rectangles. Each of the next $n$ lines contains four integers $x_1, y_1, x_2, y_2$ ($- 1000000 \leq x_1 < x_2 \leq 1000000$, $-1000000 \leq y_1 < y_2 \leq 1000000$), indicating the lower left and upper right corners of a rectangle.

Output

For each input test case, output a single integer indicating the length of the longest sequence.

Samples

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

2
1

Resources

6th BUPT Programming Contest Final