某个寒假，Twilight7在一个名叫Codeforces的著名大型多人在线交友网站上认识了名为gisp_zjz的偶像，他发现小哥哥的每一行代码写的都很漂亮，难以抑制内心悸动的他，誓要成为像小哥哥一样优秀的男孩子。后来的故事想必很多人都知道，偶像在短短几个月内成为了超级网红咖啡鸡的一员，而Twilight7还在挣扎地推着概率DP。某天深夜，正在写博客的他双手放在键盘上迷迷糊糊睡着了，Twilight7做了一个很神奇的梦，他突然穿越到了南大仙陵校区ACM实验室，看到柜子上一叠叠的金牌，转过身去，LHY就在面前，哇，终于见到偶像了，他这样想着。偶像说：“想成为和我一样厉害的人吗，那就单挑了这套区域赛题吧。”可是签到题就把Twilighty7难住了，问题是这样的，一条直线上从左至右总共有N（1<=N<=1e5）个点，有M(1<=M<=1e5)个操作，每次要从第P(1<=p<=N)个点走到第Q（p<=q<=N）个点。由于每个点有权值，每次经过点都需要加上这个权值。已知这N个点的权值是一个1到N的排列，请你构造一个排列，使得做完所有这些操作的权值和最小，并输出这个最小值。
输入描述:
多组数据、随机数据
第一行：数据组数T（1<=T<=50）
每组数据：
第一行： N和M 分别表示点的个数和操作的个数
接下来的M行：每行两个数P和Q分别表示这个操作的起始点和结束点。
输出描述:
输出做完所有这些操作后的最小值。
示例1
说明
对于样例，1号点经过了2次，2号点经过了1次，3号点经过了1次，那么对于排列1 2 3,最小值为1*2+2*1+1*3=7