Yet Another Segments Subset

## 题目描述 给你$n$个线段，每个线段用左右端点$l_i$,$r_i$表示。 现在要你从中选出尽量多的线段，使得他们两两之间要么完全不相交，要么其中一个完全包含另一个。 你需要回答$t$次询问。 ## 输入格式 第一行是一个数字$t(t\leq1000)$，表示有$t$个查询。 每个查询有$n(n\leq3000)$个线段，每个线段有两个$l_i,r_i(1\leq l_i \leq r_i\leq 2\times10^5)$代表左右边界。 同一个查询的所有线段中保证没有两个线段是完全一样的，并且数据保证所有查询的$n$起来不超过$3000$。 ## 输出格式 每个查询输出一行一个数字，代表最多能选多少个满足题意的线段。

You are given $ n $ segments on a coordinate axis $ OX $ . The $ i $ -th segment has borders $ [l_i; r_i] $ . All points $ x $ , for which $ l_i \le x \le r_i $ holds, belong to the $ i $ -th segment. Your task is to choose the maximum by size (the number of segments) subset of the given set of segments such that each pair of segments in this subset either non-intersecting or one of them lies inside the other one. Two segments $ [l_i; r_i] $ and $ [l_j; r_j] $ are non-intersecting if they have no common points. For example, segments $ [1; 2] $ and $ [3; 4] $ , $ [1; 3] $ and $ [5; 5] $ are non-intersecting, while segments $ [1; 2] $ and $ [2; 3] $ , $ [1; 2] $ and $ [2; 2] $ are intersecting. The segment $ [l_i; r_i] $ lies inside the segment $ [l_j; r_j] $ if $ l_j \le l_i $ and $ r_i \le r_j $ . For example, segments $ [2; 2] $ , $ [2, 3] $ , $ [3; 4] $ and $ [2; 4] $ lie inside the segment $ [2; 4] $ , while $ [2; 5] $ and $ [1; 4] $ are not. You have to answer $ t $ independent test cases.

The first line of the input contains one integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. Then $ t $ test cases follow. The first line of the test case contains one integer $ n $ ( $ 1 \le n \le 3000 $ ) — the number of segments. The next $ n $ lines describe segments. The $ i $ -th segment is given as two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le 2 \cdot 10^5 $ ), where $ l_i $ is the left border of the $ i $ -th segment and $ r_i $ is the right border of the $ i $ -th segment. Additional constraint on the input: there are no duplicates in the list of segments. It is guaranteed that the sum of $ n $ does not exceed $ 3000 $ ( $ \sum n \le 3000 $ ).

For each test case, print the answer: the maximum possible size of the subset of the given set of segments such that each pair of segments in this subset either non-intersecting or one of them lies inside the other one.

4
4
1 5
2 4
2 3
3 4
5
1 5
2 3
2 5
3 5
2 2
3
1 3
2 4
2 3
7
1 10
2 8
2 5
3 4
4 4
6 8
7 7

3
4
2
7