No submission language available for this problem.

Description

Input

The first line of input contains one integer $t$ ($1 \leq t \leq 5$): the number of test cases.

The next lines contains the descriptions of the test cases.

In the first line you are given two integers $n$ and $m$ ($1 \leq n \leq 150\,000$, $0 \leq m \leq \min(150\,000, \frac{n(n-1)}{2})$): the number of vertices and edges in the graph.

Each of the next $m$ lines contains two integers $a$, $b$ ($1 \leq a < b \leq n$), specifying an edge $a \to b$ in the graph. No edge $a \to b$ appears more than once.

Output

For each test case, print one integer: the number of pairs of vertices $x$, $y$, $x > y$, such that after adding the edge $x \to y$ to the graph, it has a Hamiltonian path.

Samples

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

3
1
4

Note

In the first example, any edge $x \to y$ such that $x > y$ is valid, because there already is a path $1 \to 2 \to 3$.

In the second example only the edge $4 \to 1$ is valid. There is a path $3 \to 4 \to 1 \to 2$ if this edge is added.

In the third example you can add edges $2 \to 1$, $3 \to 1$, $4 \to 1$, $4 \to 2$.