小 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 擺放一座燈塔。可以證明，呢個係滿足擁有最少燈塔數量條件嘅唯一方案。