银河系中有 $n$ 个行星，以及许多连接它们的无向虫洞。6000 年前，Spinel 对这些行星进行了一次深度优先搜索，访问了所有行星，并按照发现的顺序将它们标记为 $1$ 到 $n$。

自那时起，许多虫洞已经损坏，目前只有 $m$ 个虫洞仍然可用。Spinel 想知道，为了能够进行一次深度优先搜索，且发现顺序恰好与 6000 年前标记的顺序一致，最少需要新建多少个虫洞。

回想一下，深度优先搜索（DFS）算法以图 $G$ 和图中的一个顶点 $v$ 作为输入，并将所有从 $v$ 可达的顶点标记为已发现。

以下是 DFS 递归实现的伪代码：

procedure DFS(G, v) is
label v as discovered
for all vertices w that there exists an edge between v and w do
if vertex w is not labeled as discovered then
recursively call DFS(G, w)

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例的格式如下：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)，分别表示行星的数量和剩余虫洞的数量。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示 $u_i$ 和 $v_i$ 之间存在一个虫洞。

保证所有测试用例的 $(n + m)$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示需要新建的虫洞的最小数量。

样例

输入 1

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

输出 1

0
2
1

说明

对于第二个样例测试用例，我们可以添加一个连接行星 1 和 2 的虫洞，并添加另一个连接行星 2 和 3 的虫洞。

对于第三个样例测试用例，我们可以添加一个连接行星 2 和 3 的虫洞。