小 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$。

輸出格式

對於每組測試資料，輸出一個整數，表示需要放置的燈塔的最少數量。

範例

輸入

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 和節點 4 放置兩座燈塔。

對於第二組測試資料，可以分別在節點 2 和節點 5 放置兩座燈塔。

對於第三組測試資料，一個可行的方案是在節點 2 放置一座燈塔。可以證明，這是滿足擁有最少燈塔數量條件的唯一方案。