CF1932F.Feed Cats

There is a fun game where you need to feed cats that come and go. The level of the game consists of $n$ steps. There are $m$ cats; the cat $i$ is present in steps from $l_i$ to $r_i$, inclusive. In each step, you can feed all the cats that are currently present or do nothing.

If you feed the same cat more than once, it will overeat, and you will immediately lose the game. Your goal is to feed as many cats as possible without causing any cat to overeat.

Find the maximum number of cats you can feed.

Formally, you need to select several integer points from the segment from $1$ to $n$ in such a way that among given segments, none covers two or more of the selected points, and as many segments as possible cover one of the selected points.

有一个有趣的游戏，你需要喂养来来去去的猫。游戏的一个关卡包含 $n$ 个步骤。共有 $m$ 只猫；其中第 $i$ 只猫在步骤区间 $[l_i, r_i]$（含端点）内出现。在每个步骤中，你可以喂养所有当前在场的猫，或者什么也不做。

如果你多次喂养同一只猫，它会暴食，你将立即输掉游戏。你的目标是在不导致任何猫暴食的前提下，尽可能多地喂养猫。

求你能喂养的猫的最大数量。

形式化地，你需要从区间 $[1, n]$ 中选出若干个整数点，使得在给定的所有区间中，没有任何一个区间覆盖两个或以上的被选点，并且尽可能多的区间恰好覆盖其中一个被选点。

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 10^6$, $1 \le m\le 2\cdot 10^5$).

The $i$-th of the next $m$ lines contains a pair of integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$).

The sum of $n$ for all tests does not exceed $10^6$, the sum of $m$ for all tests does not exceed $2\cdot 10^5$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^6$，$1 \le m \le 2\cdot 10^5$）。

接下来的 $m$ 行中，第 $i$ 行包含一对整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）。

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

For each test case, print a single integer, the maximum number of cats you can feed.

对于每个测试用例，输出一个整数，表示你能喂养的猫的最大数量。

In the first example, one of the ways to feed five cats is to feed at steps $4$ and $11$.

• At step $4$, cats $1$, $2$, and $3$ will be fed.
• At step $11$, cats $5$ and $6$ will be fed.

在第一个例子中，喂养五只猫的一种方法是在第 $4$ 步和第 $11$ 步进行投喂。

• 在第 $4$ 步，将喂养第 $1$、$2$ 和 $3$ 只猫。
• 在第 $11$ 步，将喂养第 $5$ 和 $6$ 只猫。