仙人掌图（cactus）是一个连通的无向图，其中每条边最多属于一个简单环。直观地说，仙人掌图是树的一种推广，允许存在一些环。仙人掌图中不允许有重边（一对顶点之间有多条边）和自环（连接顶点自身的边）。

给定一个包含 $n$ 个顶点的有向图 $G$，其具有以下性质：考虑一个由 $n$ 个顶点构成的无向图 $G'$，其构造方式为：对于 $G$ 中的每一条有向边 $(u_i, v_i)$，在 $G'$ 中添加一条无向边 $\{u_i, v_i\}$。此时 $G'$ 是一个仙人掌图。

求 $G$ 中满足从顶点 $x$ 到顶点 $y$ 存在路径的有序顶点对 $(x, y)$ 的数量。假设从一个顶点到其自身总是存在路径。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。

接下来是各测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示 $G$ 中的顶点数和边数 ($2 \le n \le 250\,000$; $n - 1 \le m \le \lfloor \frac{3(n-1)}{2} \rfloor$)。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示 $G$ 中一条从 $u_i$ 指向 $v_i$ 的有向边 ($1 \le u_i, v_i \le n; u_i \neq v_i$)。

由无向边 $\{u_i, v_i\}$ 构成的无向图是一个仙人掌图。

保证所有测试用例的 $n$ 之和不超过 $250\,000$。

输出格式

对于每个测试用例，输出满足在 $G$ 中从顶点 $x$ 到顶点 $y$ 可达的有序对 $(x, y)$ 的数量。

样例

样例输入 1

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

样例输出 1

6
18