小 Q 是一名见习飞行员，他正在进行飞行训练。

世界上一共有 $n$ 个机场，编号依次为 $1,2,\dots,n$。在这些机场的停机坪上，停放着 $m$ 架飞机。第 $i$ 架飞机位于 $x_i$ 号机场，如果小 Q 驾驶它起飞，将被允许降落在编号在 $[l_i,r_i]$ 的任意机场。一架飞机的燃料只允许它被使用一次。

小 Q 每天将从任意机场 $x$ 挑选一架飞机 $a$ 起飞，合法地降落在机场 $y$（$y\neq x$），然后挑选机场 $y$ 的一架飞机 $b$ 起飞，合法地降落在机场 $z$（$z\neq x$, $z\neq y$），最后挑选 $z$ 的一架飞机 $c$ 起飞，合法地降落在机场 $x$，构成一天的训练计划。

小 Q 现在想知道，一共有多少种不同的训练计划？两个计划被认为不同当且仅当六元组（$a,b,c,x,y,z$）不同。

第一行包含一个正整数 $T$（$1\leq T\leq 15$），表示测试数据的组数。

每组数据第一行包含两个正整数 $n,m$（$3\leq n\leq 50\,000$, $1\leq m\leq 50\,000$），分别表示机场和飞机的数量。

接下来 $m$ 行，每行三个正整数 $x_i,l_i,r_i$（$1\leq x_i\leq n$, $1\leq l_i\leq r_i\leq n$, $x_i\notin[l_i,r_i]$），分别描述每架飞机。

输入数据保证 $\sum n\leq 200\,000$ 且 $\sum m\leq 200\,000$。

对于每组数据输出一行一个整数，即本质不同的训练计划数量。