#P18273. Staircase Museum

Staircase Museum

Staircase Museum

一座阶梯形博物馆建成了,用来展出抽象艺术作品。

将地面看作由无穷多个单位正方形格子组成的平面,格子的边平行于坐标轴。对任意一对整数 (x,y)(x,y),格子 (x,y)(x,y) 的左下角为 (x−1,y−1)(x-1,y-1),右上角为 (x,y)(x,y)。

给定两个序列 l1,l2,…,lnl_1,l_2,\ldots,l_n 和 r1,r2,…,rnr_1,r_2,\ldots,r_n,所有满足

1≤x≤n,lx≤y≤rx1\le x\le n,\qquad l_x\le y\le r_x

的格子组成博物馆。输入保证,对每个 1≤i<n1\le i<n,都有

li≤li+1≤ri≤ri+1,l_i\le l_{i+1}\le r_i\le r_{i+1},

因此博物馆是连通的阶梯形区域。

前两个样例的博物馆形状

上图从左到右分别对应前两个样例。

一群抽象艺术家准备进入博物馆。每人会在博物馆内部或边界上选定一个固定位置。欣赏抽象艺术已经足够费心,他们不希望再看见其他艺术家。

当且仅当连接两名艺术家的整条直线段都位于博物馆内部或边界上时,两人能够看见彼此。也就是说,沿边界的视线也算可见。

第二个样例中的合法和不合法位置

左图展示了第二个样例的一种合法摆放。右图不合法:红色线段连接的两人能够看见彼此。

请你求出最多能安排多少名艺术家,使任意两名艺术家都不能看见彼此。

输入格式

第一行一个整数 TT(1≤T≤1051\le T\le10^5),表示测试用例数。

对于每个测试用例:

  • 第一行一个整数 nn(1≤n≤5×1051\le n\le5\times10^5)。
  • 接下来 nn 行,第 ii 行两个整数 li,ril_i,r_i(1≤li≤ri≤1091\le l_i\le r_i\le10^9)。

对每个 1≤i<n1\le i<n,保证 li≤li+1≤ri≤ri+1l_i\le l_{i+1}\le r_i\le r_{i+1}。

同一输入文件内所有测试用例的 nn 之和不超过 5×1055\times10^5。

输出格式

对每个测试用例输出一行一个整数,表示答案。只需输出最大人数,不需要输出位置方案。

样例输入

4
3
1 2
1 3
1 3
3
1 2
2 3
3 3
3
1 1
1 3
3 3
4
1 2
2 3
3 4
4 5

样例输出

2
3
3
4