E1. Turtle and Inversions (Easy Version)
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is an easy version of this problem. The differences between the versions are the constraint on $$$m$$$ and $$$r_i < l_{i + 1}$$$ holds for each $$$i$$$ from $$$1$$$ to $$$m - 1$$$ in the easy version. You can make hacks only if both versions of the problem are solved.

Turtle gives you $$$m$$$ intervals $$$[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$$$. He thinks that a permutation $$$p$$$ is interesting if there exists an integer $$$k_i$$$ for every interval ($$$l_i \le k_i < r_i$$$), and if he lets $$$a_i = \max\limits_{j = l_i}^{k_i} p_j, b_i = \min\limits_{j = k_i + 1}^{r_i} p_j$$$ for every integer $$$i$$$ from $$$1$$$ to $$$m$$$, the following condition holds:

$$$$$$\max\limits_{i = 1}^m a_i < \min\limits_{i = 1}^m b_i$$$$$$

Turtle wants you to calculate the maximum number of inversions of all interesting permutations of length $$$n$$$, or tell him if there is no interesting permutation.

An inversion of a permutation $$$p$$$ is a pair of integers $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) such that $$$p_i > p_j$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n, m$$$ ($$$2 \le n \le 5 \cdot 10^3, 0 \le m \le \frac{n}{2}$$$) — the length of the permutation and the number of intervals.

The $$$i$$$-th of the following $$$m$$$ lines contains two integers $$$l_i, r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — the $$$i$$$-th interval.

Additional constraint on the input in this version: $$$r_i < l_{i + 1}$$$ holds for each $$$i$$$ from $$$1$$$ to $$$m - 1$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^3$$$.

Output

For each test case, if there is no interesting permutation, output a single integer $$$-1$$$.

Otherwise, output a single integer — the maximum number of inversions.

Example
Input
6
2 0
2 1
1 2
5 1
2 4
8 2
1 4
6 8
7 2
1 3
4 7
7 3
1 2
3 4
5 6
Output
1
0
8
21
15
15
Note

In the third test case, the interesting permutation with the maximum number of inversions is $$$[5, 2, 4, 3, 1]$$$.

In the fourth test case, the interesting permutation with the maximum number of inversions is $$$[4, 8, 7, 6, 3, 2, 1, 5]$$$. In this case, we can let $$$[k_1, k_2] = [1, 7]$$$.

In the fifth test case, the interesting permutation with the maximum number of inversions is $$$[4, 7, 6, 3, 2, 1, 5]$$$.

In the sixth test case, the interesting permutation with the maximum number of inversions is $$$[4, 7, 3, 6, 2, 5, 1]$$$.