G. 网格游戏
每个测试的时间限制：4 秒
内存限制：1024 MB

克莱尔喜欢画线。她收到一张 $n \times n$ 的格子纸，并开始在纸上画“线”。不过，这里的“线”不是通常意义上的直线——克莱尔所说的“线”指的是一列中连续的几个格子（垂直方向连续）。当她画一条线时，这些格子都会涂成黑色。一开始所有格子都是白色，画线会涂黑一些格子。画完若干条线后，克莱尔想知道：有多少种方法，可以把另一个白色格子涂黑，使得剩下的白色格子不再构成一个连通块。

两个格子如果有公共边，则称它们直接连通。
如果存在一个格子序列 $c_0, c_1, \dots, c_k$（$k>1$），使得 $c_0 = x$，$c_k = y$，且对每个 $i \in \{1,2,\dots,k\}$，$c_i$ 与 $c_{i-1}$ 直接连通，则称 $x$ 与 $y$ 间接连通。
若一组白色格子中任意两个格子（直接或间接）连通，则这组格子构成一个连通块。

网格有 $n$ 行 $n$ 列，行和列都从 $1$ 到 $n$ 编号。
克莱尔会画 $q$ 条线。第 $i$ 条线位于第 $y_i$ 列，从第 $s_i$ 行到第 $f_i$ 行，其中 $s_i \le f_i$。注意：至少被一条线经过的格子都会涂成黑色。下图是一个 $20 \times 20$ 网格，$q = 67$ 条线的例子。红星星标记的格子，如果涂黑它们，所有白色格子将不再组成一个连通块。

可以假设：画完 $q$ 条线后，剩下的白色格子构成一个连通块，且至少包含 $3$ 个白色格子。

输入
第一行包含一个整数 $t$，表示测试数据组数。
对于每组数据：
第一行包含两个整数 $n$ 和 $q$。
接下来 $q$ 行，每行三个整数 $y_i, s_i, f_i$。

数据范围：

• $1 \le t \le 125$
• $2 \le n \le 10^9$
• $q \ge 1$，所有测试用例的 $q$ 之和 $\le 10^5$
• $1 \le y_i \le n$
• $1 \le s_i \le f_i \le n$
• 至少有三个白色格子，且所有白色格子构成一个连通块。

输出
每行输出一个整数，表示有多少种方式涂黑一个额外的白色格子，使得剩下的白色格子不再构成一个连通块。

样例

输入

2
3 1
2 1 2
5 2
2 1 4
4 2 5

输出

5
15