Little 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}$ を結ぶ辺が存在します。また、サイクル上のすべての頂点を順に結ぶ辺の集合をそのサイクルの辺集合と呼び、2 つのサイクルはそれらの辺集合が異なる場合かつその場合に限り異なるサイクルとみなされます。Little Y が散策を続けるうちに、ある性質を発見しました。グラフ内の各辺は高々 1 つのサイクルにしか含まれないのです。

現在、公園には照明設備がないため、夜になると公園は完全に真っ暗になってしまいます。幸いなことに、スタッフは地図上のいくつかの頂点に灯台を設置しようとしています。グラフ上の 2 つの頂点間の距離は、一方の頂点から他方の頂点へ到達するために通過しなければならない最小の辺数として定義されます。したがって、各灯台は設置された頂点を照らすだけでなく、設置された頂点からの距離が $k$ 以下のすべての頂点も照らすことができます。

競技プログラミングの参加者である Little Y は、自然とある疑問を思いつきました。すべての頂点を確実に照らすためには、最小でいくつの灯台を設置する必要があるでしょうか？

入力

この問題には複数のテストケースが含まれます。入力の 1 行目には、テストケースの個数を表す整数 $T$（$1 \le T \le 10^5$）が与えられます。

各テストケースについて：

1 行目には、地図上の頂点数と辺数、および灯台が照らすことのできる最大距離を表す 3 つの整数 $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$ 行には、地図上の辺を表す 2 つの整数 $u, v$（$1 \le u, v \le n, u \ne v$）がそれぞれ与えられます。

与えられる無向グラフは連結であり、多重辺や自己ループを持たず、各辺は高々 1 つのサイクルにしか含まれないことが保証されます。また、すべてのテストケースにおける $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

出力

2
2
1

注記

1 番目のテストケースでは、頂点 1 と頂点 4 にそれぞれ灯台を 1 つずつ（計 2 つ）設置することができます。

2 番目のテストケースでは、頂点 2 と頂点 5 にそれぞれ灯台を 1 つずつ（計 2 つ）設置することができます。

3 番目のテストケースでは、実行可能な解の 1 つは頂点 2 に灯台を 1 つ設置することです。灯台の個数を最小にする条件を満たす解はこれに限ることが証明できます。