Codeforces Round 927 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dp

sortings

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Feed Cats

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThere 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.

Example

Input

315 62 103 52 47 78 1211 111000 11 10005 101 23 43 43 43 41 11 23 33 43 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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/16/2024 02:29:49 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|