Description

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.

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

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.