题目描述

在二维平面上有 $n$ 条线段，第 $i$ 条线段的两个端点分别为 $(l_i, i)$ 和 $(r_i, i)$。你可以在平面上的任意整数点上放任意多个“标记”（整数点指 $x$ 和 $y$ 坐标均为整数的点），但所有标记的 $x$ 坐标必须各不相同。

求最多能有多少条线段上至少有一个标记。

输入格式

输入的第一行为一个整数 $T$（约为 $100$），表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示线段的数量。

接下来的 $n$ 行，每行包含两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le 10^9$），表示第 $i$ 条线段两个端点的 $x$ 坐标。

保证至多有 $5$ 组测试数据满足 $n \ge 100$。

输出格式

对于每组测试数据，输出一行一个整数，表示最多能有多少条线段上至少放有一个标记。

2
3
1 2
1 1
2 3
3
1 2
1 1
2 2

3
2

提示

对于第一个样例，可以分别在 $(1, 2), (2, 1)$ 和 $(3, 3)$ 上放置三个标记。

对于第二个样例，可以分别在 $(1, 2)$ 和 $(2, 3)$ 上放置两个标记。

由 ChatGPT 5 翻译