考虑一个被分为 $10^6$ 段弧的圆，这些弧按顺时针方向编号为 $1$ 到 $10^6$。此外，圆上有 $n$ 个线段，每一段都覆盖了圆上的一段连续弧区间。
求满足以下条件的最大线段集合的大小：集合中任意两条线段都至少共享一段公共弧。
输入格式
输入的第一行包含测试用例的数量 $z$。接下来是各测试用例的描述。
每个测试用例的第一行包含线段数量 $n$ ($1 \le n \le 3000$)。接下来的 $n$ 行每行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i, r_i \le 10^6$)，表示第 $i$ 条线段按顺时针方向遍历时所覆盖的起始弧和结束弧。
没有线段覆盖整个圆，且没有两条线段完全重合。
所有测试用例的 $n$ 之和不超过 $24000$。
输出格式
对于每个测试用例，输出一行，包含一个整数，表示满足任意两条线段都相交的最大线段集合的大小。
样例
样例输入 1
1 4 1 4 4 5 5 2 3 3
样例输出 1
3