小 Y 正在游览一个公园。公园的地图可以表示为一个包含 $n$ 个节点和 $m$ 条边的无向简单连通图。为了帮助游客规划路线，地图中存在若干个环；每个环都可以表示为一个由不同节点组成的序列 $e_1, e_2, \dots, e_l$，其中 $l \ge 3$，且对于所有 $1 \le i \le l$，图中都存在一条连接 $e_i$ 和 $e_{(i \bmod l)+1}$ 的边。此外，在环上按顺序连接所有节点的边集被称为该环的边集，当且仅当两个环的边集不同时，它们被认为是不同的环。随着小 Y 继续游览，他发现了一个性质：图中的每条边最多只出现在一个环中。

目前，公园里还没有照明系统，所以当夜幕降临时，公园将完全陷入黑暗。幸运的是，工作人员正准备在地图上的某些节点上放置灯塔。图中两个节点之间的距离定义为从一个节点到达另一个节点所必须经过的最少边数。因此，每个灯塔除了能照亮其所在的节点外，还能照亮所有与该节点的距离不超过 $k$ 的节点。

作为一名算法竞赛选手，小 Y 自然想到了一个问题：最少需要放置多少个灯塔，才能确保所有节点都被照亮？

输入格式

本题包含多个测试用例。输入的第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例：

第一行包含三个整数 $n, m, k$ ($2 \le n \le 2 \times 10^5$, $n-1 \le m \le 2 \times 10^5$, $1 \le k \le n$)，分别表示地图上的节点数、边数，以及灯塔能够照亮的最大距离。

接下来的 $m$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \ne v$)，表示地图上的一条边。

保证给定的无向图是连通的，且没有重边或自环，并且每条边最多出现在一个环中。此外，所有测试用例中 $n$ 和 $m$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示需要放置的灯塔的最少数量。

样例

输入样例 1

3
5 4 1
1 2
1 3
3 4
1 5
5 5 1
1 2
2 3
3 4
4 5
5 1
8 8 2
1 2
2 3
3 4
4 5
5 1
1 6
2 7
3 8

输出样例 1

2
2
1

说明

对于第一个测试用例，可以分别在节点 1 和节点 4 放置两个灯塔。

对于第二个测试用例，可以分别在节点 2 和节点 5 放置两个灯塔。

对于第三个测试用例，一个可行的方案是在节点 2 放置一个灯塔。可以证明，这是满足拥有最少灯塔数量条件的唯一方案。