Claire 喜欢画线。她收到了一张 $n \times n$ 网格的纸，并开始在上面画“线”。不过，这里的“线”概念与我们通常所想的有所不同。Claire 将每条“线”定义为一组连续的垂直网格单元格。当她画一条线时，这些单元格都会被黑墨水覆盖。最初，所有单元格都是白色的，画线会将其中一些单元格变成黑色。在画了几条线之后，Claire 想知道：有多少种方法可以额外将一个白色单元格涂成黑色，使得剩下的白色单元格不再构成单个连通分量。

如果两个单元格共享一条边，则它们是直接相连的。如果存在一个单元格序列 $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$。Claire 将画 $q$ 条线。第 $i$ 条线画在第 $y_i$ 列，从第 $s_i$ 行到第 $f_i$ 行，其中对于每个 $i \in \{1, 2, \dots, q\}$ 均有 $s_i \le f_i$。请注意，被这 $q$ 条线中至少一条穿过的单元格都会被染成黑色。下图显示了一个 $20 \times 20$ 网格且 $q = 67$ 条线的例子。网格中用红色星号标记的单元格表示：如果 Claire 将该单元格涂成黑色，则所有剩余的白色单元格将不再构成单个连通分量。

你可以假设，在画出这 $q$ 条线后，剩余的白色单元格构成一个包含至少三个白色单元格的单个连通分量。

输入格式

第一行包含恰好一个整数 $t$，表示测试用例的数量。对于每个测试用例，首先包含一行，其中恰好有两个整数 $n$ 和 $q$。这表示网格大小为 $n \times n$，且 Claire 在其上画了 $q$ 条线。接下来有 $q$ 行。对于每个 $i \in \{1, 2, \dots, q\}$，这 $q$ 行中的第 $i$ 行恰好包含三个整数 $y_i$、$s_i$ 和 $f_i$。

数据范围

• $1 \le t \le 125$
• $2 \le n \le 10^9$
• $q \ge 1$；所有 $q$ 的总和最多为 $10^5$
• $1 \le y_i \le n$
• $1 \le s_i \le f_i \le n$
• 至少存在三个白色单元格，且所有白色单元格构成一个连通分量。

输出格式

对于每个测试用例，在一行中输出一个整数，表示 Claire 有多少种方法可以额外将一个白色单元格涂成黑色，使得剩下的白色单元格不再构成单个连通分量。

样例

输入格式 1

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

输出格式 1

5
15