P16348 「MierOI R1」Eternal (Hard ver.)

本题是 [P16280](https://www.luogu.com.cn/problem/P16280) 的加强版。两个版本唯一的区别是，在本题中，$n \le 5 \times 10^4$。

给定 $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$。

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

#### 「样例 #1 解释」 对于第一组测试数据，可选取 $[1,1],[1,3]$ 两个区间。可以证明，不存在选取更多区间的方案。 对于第二组测试数据，可选取 $[1,3],[2,3],[4,5],[3,5]$ 四个区间。可以证明，不存在选取更多区间的方案。 #### 「数据范围」 **本题不设部分分。** 对于所有测试数据，保证 $1 \le T \le 5$，$1 \le n \le 5 \times 10^4$，$1 \le l_i \le r_i \le 2n$。