Hossam 举办了一场盛大的聚会,他将邀请他的朋友参加聚会。
他有 $$$n$$$ 个朋友,编号从 $$$1$$$ 到 $$$n$$$。它们将按如下方式排列在队列中:$$$1, 2, 3, \ldots, n$$$。
Hossam 有一张他的 $$$m$$$ 不认识朋友的列表。任何未出现在该列表中的配对都是朋友。
从朋友 $$$a$$$ 开始到朋友 $$$b$$$ 结束的队列子段是 $$$[a, a + 1, a + 2, \ldots, b]$$$。当队列的所有子段都是朋友时,该子段被称为良好。
Hossam 想知道有多少对 $$$(a, b)$$$ ($$$1 \le a \le b \le n$$$),这样从朋友 $$$a$$$ 开始到朋友 $$$b$$$ 结束的子段是好的。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$),测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le m \le 10^5$$$),分别代表朋友的数量和配对的数量。
接下来的 $$$m$$$ 行的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i\le n$$$, $$$x_i \neq y_i$$$),代表 Hossam 的一对互相不认识的朋友。
请注意,配对可以重复。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$,所有测试用例的$$$m$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,打印一个整数 - 良好子段的数量。
示例
输入 #1
2 3 2 1 3 2 3 4 2 1 2 2 3
输出 #1
4 5
注意
在第一个示例中,答案是 $$$4$$$。
好的细分是:
[1]
[2]
[3]
[1, 2]
在第二个示例中,答案是 $$$5$$$。
好的细分是:
[1]
[2]
[3]
[4]
[3, 4]