考虑以下在线性代数教科书中常见的练习题。

设 $A$ 为一个 $n \times n$ 的矩阵。证明以下命题是等价的：

• (a) $A$ 是可逆的。
• (b) 对于每个 $n \times 1$ 的矩阵 $b$，$Ax = b$ 恰好有一个解。
• (c) 对于每个 $n \times 1$ 的矩阵 $b$，$Ax = b$ 是相容的。
• (d) $Ax = 0$ 只有平凡解 $x = 0$。

解决此类练习的典型方法是证明一系列推导关系。例如，可以通过证明 (a) 推出 (b)、(b) 推出 (c)、(c) 推出 (d) 以及最后 (d) 推出 (a) 来进行。这四个推导关系证明了这四个命题是等价的。

另一种方法是证明 (a) 与 (b) 等价（通过证明 (a) 推出 (b) 且 (b) 推出 (a)）、(b) 与 (c) 等价、以及 (c) 与 (d) 等价。然而，这种方法需要证明六个推导关系，这显然比只证明四个推导关系要多做很多工作！

我现在收到了一些类似的任务，并且已经开始证明了一些推导关系。现在我想知道，我还需要再证明多少个推导关系？你能帮我确定这个数量吗？

输入格式

第一行包含一个正整数：测试用例的数量，最多为 100。

对于每个测试用例：

• 一行包含两个整数 $n$（$1 \le n \le 20\,000$）和 $m$（$0 \le m \le 50\,000$）：命题的数量以及已经证明的推导关系的数量。
• $m$ 行，每行包含两个整数 $s_1$ 和 $s_2$（$1 \le s_1, s_2 \le n$ 且 $s_1 \neq s_2$），表示已经证明了命题 $s_1$ 可以推出命题 $s_2$。

输出格式

对于每个测试用例：

• 输出一行，包含为了证明所有命题等价而需要证明的最少额外推导关系数量。

样例

输入样例 1

2
4 0
3 2
1 2
1 3

输出样例 1

4
2