CF1399F.Yet Another Segments Subset

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.

给你 $n$ 条位于坐标轴 $OX$ 上的线段。第 $i$ 条线段的端点为 $[l_i; r_i]$。所有满足 $l_i \le x \le r_i$ 的点 $x$ 均属于第 $i$ 条线段。

你的任务是从给定的线段集合中选出一个最大（包含线段数量最多）的子集，使得该子集中任意两条线段要么互不相交，要么其中一条完全位于另一条内部。

两条线段 $[l_i; r_i]$ 和 $[l_j; r_j]$ 互不相交，当且仅当它们没有公共点。例如，线段 $[1; 2]$ 与 $[3; 4]$、$[1; 3]$ 与 $[5; 5]$ 是互不相交的；而线段 $[1; 2]$ 与 $[2; 3]$、$[1; 2]$ 与 $[2; 2]$ 是相交的。

线段 $[l_i; r_i]$ 位于线段 $[l_j; r_j]$ 内部，当且仅当 $l_j \le l_i$ 且 $r_i \le r_j$。例如，线段 $[2; 2]$、$[2; 3]$、$[3; 4]$ 和 $[2; 4]$ 均位于线段 $[2; 4]$ 内部；而 $[2; 5]$ 和 $[1; 4]$ 不在 $[2; 4]$ 内部。

你需要处理 $t$ 个相互独立的测试用例。

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$).

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3000$），表示线段的数量。接下来的 $n$ 行描述这些线段。第 $i$ 个线段由两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le 2 \cdot 10^5$）给出，其中 $l_i$ 是第 $i$ 个线段的左端点，$r_i$ 是第 $i$ 个线段的右端点。

输入的额外约束：线段列表中不存在重复线段。

保证所有测试用例中 $n$ 的总和不超过 $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.

对于每个测试用例，输出答案：在给定的线段集合中，所能选出的满足如下条件的最大子集的大小——该子集中任意两条线段要么不相交，要么其中一条完全位于另一条内部。