Little Y sedang mengunjungi sebuah taman. Peta taman ini dapat direpresentasikan oleh graf terhubung sederhana tak berarah yang memuat $n$ simpul dan $m$ sisi. Untuk membantu wisatawan merencanakan rute mereka, terdapat beberapa siklus pada peta; setiap siklus dapat direpresentasikan oleh barisan simpul berbeda $e_1, e_2, \dots, e_l$, dengan $l \ge 3$, dan untuk semua $1 \le i \le l$, terdapat sebuah sisi pada graf yang menghubungkan $e_i$ dan $e_{(i \bmod l)+1}$. Selain itu, himpunan sisi yang menghubungkan semua simpul secara berurutan pada siklus disebut himpunan sisi dari siklus tersebut, dan dua siklus dianggap berbeda jika dan hanya jika himpunan sisinya berbeda. Saat Little Y melanjutkan kunjungannya, ia menemukan sebuah sifat: setiap sisi pada graf muncul dalam paling banyak satu siklus.

Saat ini, belum ada sistem pencahayaan di taman, sehingga ketika malam tiba, taman akan menjadi gelap gulita. Untungnya, staf taman sedang bersiap untuk menempatkan mercusuar di beberapa simpul pada peta. Jarak antara dua simpul pada graf didefinisikan sebagai jumlah sisi minimum yang harus dilalui untuk mencapai satu simpul dari simpul lainnya. Oleh karena itu, setiap mercusuar, selain menerangi simpul tempatnya berada, juga dapat menerangi semua simpul yang berjarak tidak lebih dari $k$ dari simpul penempatannya.

Sebagai peserta pemrograman kompetitif, Little Y secara alami memikirkan sebuah pertanyaan: berapa jumlah minimum mercusuar yang perlu ditempatkan untuk memastikan bahwa semua simpul diterangi?

Masukan

Soal ini berisi beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^5$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji:

Baris pertama berisi tiga bilangan bulat $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$), yang masing-masing menyatakan banyaknya simpul dan sisi pada peta, serta jarak maksimum yang dapat diterangi oleh sebuah mercusuar.

$m$ baris berikutnya masing-masing berisi dua bilangan bulat $u, v$ ($1 \le u, v \le n, u \ne v$), yang menyatakan sebuah sisi pada peta.

Dijamin bahwa graf tak berarah yang diberikan terhubung serta tidak memiliki sisi ganda maupun gelung (self-loop), dan setiap sisi muncul dalam paling banyak satu siklus. Selain itu, jumlah total $n$ dan $m$ di seluruh kasus uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan sebuah bilangan bulat yang menyatakan jumlah minimum mercusuar yang perlu ditempatkan.

Contoh

Masukan

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

Keluaran

2
2
1

Catatan

Untuk kasus uji pertama, dua mercusuar dapat ditempatkan masing-masing di simpul 1 dan simpul 4.

Untuk kasus uji kedua, dua mercusuar dapat ditempatkan masing-masing di simpul 2 dan simpul 5.

Untuk kasus uji ketiga, salah satu solusi yang layak adalah menempatkan sebuah mercusuar di simpul 2. Dapat dibuktikan bahwa ini adalah satu-satunya solusi yang memenuhi syarat jumlah mercusuar minimum.