题目描述

给定 $n$ 个闭区间 $[l_1,r_1],[l_2,r_2],\dots,[l_n,r_n]$。求最多能选取多少个区间，使所选区间中任意两个 相交$^{\bm{\dagger}}$ 的区间均 有公共端点$^{\bm{\ddagger}}$。

$\bm\dagger$ 称两个闭区间 $[l_1,r_1],[l_2,r_2]$ 相交，当且仅当 $l_2 \le r_1$ 且 $l_1 \le r_2$。
$\bm\ddagger$ 称两个闭区间 $[l_1,r_1],[l_2,r_2]$ 有公共端点，当且仅当 $l_1=l_2$，$l_1=r_2$，$r_1=l_2$ 或 $r_1=r_2$。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $T$，表示测试数据的组数。

接下来依次输入 $T$ 组测试数据。对于每组测试数据：

• 第一行，一个正整数 $n$。
• 接下来 $n$ 行，每行两个正整数 $l_i,r_i$。

输出格式

对于每组测试数据，输出一行一个整数，表示所选区间个数的最大值。

4
3
1 3
2 2
1 1
5
1 3
2 3
4 5
3 5
1 4
8
1 4
2 4
3 4
1 2
2 3
1 3
3 5
4 5
16
1 4
2 4
3 4
1 2
2 3
1 3
3 5
4 5
5 8
6 8
7 8
5 6
6 7
5 7
7 9
8 9

2
4
6
12

提示

「样例 #1 解释」

对于第一组测试数据，可选取 $[1,1],[1,3]$ 两个区间。可以证明，不存在选取更多区间的方案。

对于第二组测试数据，可选取 $[1,3],[2,3],[4,5],[3,5]$ 四个区间。可以证明，不存在选取更多区间的方案。

「数据范围」

本题采用子任务捆绑测试。

对于所有测试数据，保证 $1 \le T \le 5$，$1 \le n \le 1\,000$，$1 \le l_i \le r_i \le 2n$。

::cute-table{tuack}

• 特殊性质 A：给定的任意两个区间均无公共端点。
• 特殊性质 B：给定的任意两个区间均相交。