喂猫

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

游戏共有 $n$ 个时刻，有 $m$ 只猫。第 $i$ 只猫只会在闭区间 $[l_i,r_i]$ 内出现。

在每个时刻 $x$，你可以选择喂食；此时所有满足 $l_i\le x\le r_i$ 的猫都会被喂一次。你也可以什么都不做。如果某只猫被喂了至少两次，它就会死亡。

在不让任何猫死亡的前提下，最多能让多少只猫被喂至少一次？

输入格式

第一行一个整数 $t$，表示测试用例数。

每个测试用例第一行包含 $n,m$。接下来 $m$ 行每行包含 $l_i,r_i$。

输出格式

对每个测试用例输出一行一个整数，表示最多能被喂到的猫数。

样例输入 1

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

样例输出 1

5
1
10

数据范围

对于所有数据，$1\le t\le10^4$，$1\le n$，$1\le m$，$1\le l_i\le r_i\le n$；每个输入文件满足 $\sum n\le10^6$ 且 $\sum m\le2\times10^5$。