Problem Description

There are $N$ cities in Codeland.
The President of Codeland has a plan to construct one-way roads between them.
His plan is to construct $M$ roads.
But CRB recognized that in this plan there are many redundant roads.
So he decided to report better plan without any redundant roads to President.
Help him!
The road ($u$, $v$) is redundant if and only if there exists a route from $u$ to $v$ without using it.

Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains two integers $N$ and $M$ denoting the number of cities and the number of roads in the President’s plan.
Then $M$ lines follow, each containing two integers $u$ and $v$ representing a one-way road from $u$ to $v$.
1 ≤ $T$ ≤ 20
1 ≤ $N$ ≤ 2 * $10^{4}$
1 ≤ $M$ ≤ $10^{5}$
1 ≤ $u$, $v$ ≤ $N$
The given graph is acyclic, and there are neither multiple edges nor self loops.

Output

For each test case, output total number of redundant roads.

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

2

Author

KUT（DPRK）