Salem 决定推出一项拼车服务，将有空座的司机与顺路的乘客连接起来。与其它交通方式相比，乘客支付的费用很少，而司机可以在不浪费时间的情况下赚取收入。乘车费用主要取决于起点和终点之间的距离。为了在市场竞争中胜出，Salem 决定对任意两点之间存在多条路径的情况免收服务费。为简化起见，我们可以假设他开展服务的城市被建模为一个具有 $N$ 个节点和 $M$ 条边的无向图。所有边的长度均为 $1$ 个单位。路径是由一系列互不相同的节点组成的序列。一条路径连接两个节点。Salem 需要你的帮助来计算其服务的初步收入，方法是计算所有满足“两点之间有且仅有一条路径”的节点对之间的距离，并忽略所有两点之间存在多于一条路径的情况。在你的收入分析中，你必须只计算每对节点一次。

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量 ($1 \le T \le 50$)。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ ($1 \le N \le 50,000$) 和 $M$ ($0 \le M \le 150,000$)，分别表示城市中的节点数和边数。它们由一个空格分隔。接下来的 $M$ 行，每行包含一对整数 $x$ 和 $y$ ($1 \le x, y \le N$)，由一个空格分隔，表示节点 $x$ 与节点 $y$ 相连。保证输入中任意两个节点之间不会有多于一条边，也不会有节点到自身的边。

输出格式

对于每个测试用例，打印一行，包含一个整数，表示所有满足“两点之间有且仅有一条路径”的节点对之间的距离之和。

样例

输入 1

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

输出 1

2
9

说明

警告：输入数据量较大，请在某些编程语言中注意效率。