活动安排

题目描述

Y 同学所在的乐园即将举办一系列精彩的活动。乐园中共有 $N$ 个待举办的活动，编号为 $1$ 到 $N$。遗憾的是，乐园内只有一个活动大厅，这意味着在同一时刻，大厅内只能进行一个活动。

已知第 $i$ 个活动的举办时间为一个半开区间 $[l_i, r_i)$。这表示该活动从时刻 $l_i$ 开始，到时刻 $r_i$ 结束。具体来说，活动占用大厅的时间段包含 $l_i$，但不包含 $r_i$。因此，如果一个活动在时刻 $t$ 结束，另一个活动可以在时刻 $t$ 立即开始。

Y 同学作为乐园的管理者，希望能够合理安排活动，使得在不发生时间冲突的前提下，能够举办的活动数量最多。请你帮他计算最多能完成多少个活动。

输入格式

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

对于每组测试数据： 第一行包含一个整数 $N$，表示活动的数量。 接下来 $N$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示第 $i$ 个活动的开始时间和结束时间。

输出格式

对于每组测试数据，输出一行一个整数，表示最多能完成的活动数量。

样例

样例输入 #1

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

样例输出 #1

2
1

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le T \le 10^3$，$\sum N \le 2 \times 10^5$，$1 \le l_i < r_i \le 10^9$。