在坐标轴 $$$OX$$$ 上给定 $$$n$$$ 段。第 $$$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]$$$ 不是。
您必须回答 $$$t$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$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$$$ 段的右边界。第$$$i$$$段。
输入的附加约束:段列表中没有重复项。
保证$$$n$$$的总和不超过$$$3000$$$ ($$$\sum n \le 3000$$$)。
输出
对于每个测试用例,打印答案:给定线段集的子集的最大可能大小,使得该子集中的每一对线段要么不相交,要么其中一个位于另一个线段内部。
示例
输入 #1
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
输出 #1
3 4 2 7