While attending the Pre-SDOI Training Camp (also known as "Public Easy Round #2") hosted by country P, you encountered the following problem:

Given a directed graph $G$ with $n$ vertices and $m$ edges, it is guaranteed that its underlying undirected graph $G'$ is a cactus and contains no multiple edges or self-loops. You need to find the number of ordered pairs $(x, y)$ such that there exists a path from $x$ to $y$ in $G$. Specifically, $(x, x)$ must also be counted in the answer.

Definition of a cactus: A connected simple undirected graph where every edge belongs to at most one simple cycle.

Definition of an underlying graph: For a directed graph $G=(V, E)$, define a new undirected graph $G'=(V, E')$, where $E'$ is the set of edges obtained by replacing every directed edge in $E$ with an undirected edge. $G'$ is called the underlying graph of $G$.

Input

The first line contains a positive integer $T$, representing the number of test cases. For each test case:

• The first line contains two positive integers $n$ and $m$.
• The next $m$ lines each contain two positive integers $u$ and $v$, representing a directed edge from $u$ to $v$.

Output

For each test case:

• A non-negative integer representing the answer.

Examples

Input 1

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

Output 1

6
18

Input 2

See provided files.

Constraints

For all test cases, it is guaranteed that $1 \le T \le 10^5$, $2 \le n \le 2.5\times 10^5$, $n-1 \le m \le \left\lfloor \dfrac{3(n-1)}{2}\right\rfloor$, and $\sum n \le 2.5\times 10^5$.