Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 4120
Tokens on the Segments

Time Limit: 1 Second      Memory Limit: 65536 KB

Consider $n$ segments on a two-dimensional plane, where the endpoints of the $i$-th segment are $(l_i, i)$ and $(r_i, i)$. One can put as many tokens as he likes on the integer points of the plane (recall that an integer point is a point whose $x$ and $y$ coordinates are both integers), but the $x$ coordinates of the tokens must be different from each other.

What's the maximum possible number of segments that have at least one token on each of them?

#### Input

The first line of the input contains an integer $T$ (about 100), indicating the number of test cases. For each test case:

The first line contains one integer $n$ ($1 \le n \le 10^5$), indicating the number of segments.

For the next $n$ lines, the $i$-th line contains 2 integers $l_i, r_i$ ($1 \le l_i \le r_i\le 10^9$), indicating the $x$ coordinates of the two endpoints of the $i$-th segment.

It's guaranteed that at most 5 test cases have $n \ge 100$.

#### Output

For each test case output one line containing one integer, indicating the maximum possible number of segments that have at least one token on each of them.

#### Sample Input

2
3
1 2
1 1
2 3
3
1 2
1 1
2 2


#### Sample Output

3
2


#### Hint

For the first sample test case, one can put three tokens separately on (1, 2), (2, 1) and (3, 3).

For the second sample test case, one can put two tokens separately on (1, 2) and (2, 3).

Author: CHEN, Shihan
Source: The 10th Shandong Provincial Collegiate Programming Contest
Submit    Status