311091: CF1932F. Feed Cats

F. Feed Catstime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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

ExampleInput

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

Output

5
1
10

Note

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.

题目大意：有一个游戏，需要你在不同的时间喂食来来去去的猫。游戏分为n个步骤，有m只猫，第i只猫在步骤l_i到r_i之间出现。每个步骤你可以选择喂所有在场的猫或者什么都不做。如果你喂同一只猫超过一次，它就会吃撑，游戏立即失败。目标是喂尽可能多的猫，但不能让任何猫吃撑。正式地说，就是从1到n的线段中选择几个整数点，使得没有一个给定线段覆盖两个或更多的所选点，并且尽可能多的线段覆盖一个所选点。

输入数据格式：第一行输入一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。接下来是每个测试用例的描述。每个测试用例的第一行包含两个整数n和m（1 ≤ n ≤ 10^6，1 ≤ m ≤ 2×10^5）。接下来的m行，每行包含一对整数l_i和r_i（1 ≤ l_i ≤ r_i ≤ n）。所有测试的n之和不超过10^6，m之和不超过2×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
```

注意：在第一个例子中，喂五只猫的一种方法是分别在步骤4和步骤11喂食。在步骤4，猫1、2和3会被喂食。在步骤11，猫5和猫6会被喂食。题目大意：有一个游戏，需要你在不同的时间喂食来来去去的猫。游戏分为n个步骤，有m只猫，第i只猫在步骤l_i到r_i之间出现。每个步骤你可以选择喂所有在场的猫或者什么都不做。如果你喂同一只猫超过一次，它就会吃撑，游戏立即失败。目标是喂尽可能多的猫，但不能让任何猫吃撑。正式地说，就是从1到n的线段中选择几个整数点，使得没有一个给定线段覆盖两个或更多的所选点，并且尽可能多的线段覆盖一个所选点。 输入数据格式：第一行输入一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。接下来是每个测试用例的描述。每个测试用例的第一行包含两个整数n和m（1 ≤ n ≤ 10^6，1 ≤ m ≤ 2×10^5）。接下来的m行，每行包含一对整数l_i和r_i（1 ≤ l_i ≤ r_i ≤ n）。所有测试的n之和不超过10^6，m之和不超过2×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 ``` 注意：在第一个例子中，喂五只猫的一种方法是分别在步骤4和步骤11喂食。在步骤4，猫1、2和3会被喂食。在步骤11，猫5和猫6会被喂食。