F. 喂猫问题
每个测试的时间限制：3 秒
内存限制：512 兆字节

题目描述

有一个有趣的游戏，你需要喂那些来来去去的猫。这个游戏关卡由 $n$ 个步骤组成。
一共有 $m$ 只猫；第 $i$ 只猫在步骤 $l_i$ 到 $r_i$（包含两端）期间出现。
在每个步骤中，你可以选择喂食当前所有在场的猫，或者什么都不做。

如果同一只猫被喂了超过一次，它就会吃撑，游戏立即失败。
你的目标是在不导致任何猫吃撑的情况下，喂尽可能多的猫。

你需要找出最多可以喂多少只猫。

形式化定义

你需要从区间 $[1, n]$ 中选择若干个整数点（步骤），使得：

• 在给定的 $m$ 个区间（猫的出现时间段）中，没有一个区间覆盖了两个或更多选中的点（即每个区间最多包含一个你选择的点）；
• 同时，要最大化有多少个区间（猫）至少覆盖了一个选中的点（即被喂过一次）。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
接下来是每个测试用例的描述：

• 第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^6$，$1 \le m \le 2 \cdot 10^5$）。
• 接下来 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示第 $i$ 只猫的出现区间。

所有测试用例的 $n$ 之和不超过 $10^6$，所有测试用例的 $m$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示最多可以喂的猫的数量。

示例

输入：

3
15 6
2 10
3 5
2 4
7 7
8 12
11 11
1000 1
1 1000
5 10
1 2
3 4
3 4
3 4
3 4
1 1
1 2
3 3
3 4
3 4

输出：

5
1
10

第一个样例解释

一种喂 5 只猫的方法是选择步骤 $4$ 和 $11$：

• 在步骤 $4$，喂猫 $1$、$2$ 和 $3$。
• 在步骤 $11$，喂猫 $5$ 和 $6$。

这样共喂了 $5$ 只猫。