小 $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$。

输出格式

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

样例

输入

2
3 3
1 2 2
2 3 3
3 1 1
6 7
1 2 4
2 1 1
2 4 5
6 1 5
5 2 3
3 5 6
4 1 3

输出

3
15