Little Y vierailee puistossa. Tämän puiston kartta voidaan esittää suuntaamattomana yksinkertaisena yhtenäisenä verkkona, jossa on $n$ solmua ja $m$ kaarta. Jotta matkailijoiden olisi helpompi suunnitella reittejään, kartassa on useita syklejä; jokainen sykli voidaan esittää erillisten solmujen jonona $e_1, e_2, \dots, e_l$, missä $l \ge 3$, ja kaikilla $1 \le i \le l$ verkossa on kaari, joka yhdistää solmut $e_i$ ja $e_{(i \bmod l)+1}$. Lisäksi kaikkia syklin solmuja järjestyksessä yhdistävien kaarten joukkoa kutsutaan syklin kaarijoukoksi, ja kahta sykliä pidetään erilaisina jos ja vain jos niiden kaarijoukot ovat erilaiset. Jatkaessaan vierailuaan Little Y havaitsi ominaisuuden: jokainen verkon kaari esiintyy korkeintaan yhdessä syklissä.

Tällä hetkellä puistossa ei ole valaistusjärjestelmää, joten yön laskeutuessa puisto on täysin pimeä. Onneksi henkilökunta valmistautuu sijoittamaan majakoita joihinkin kartan solmuihin. Verkon kahden solmun välinen etäisyys määritellään pienimmäksi kaarten määräksi, joka on kuljettava päästäkseen solmusta toiseen. Näin ollen jokainen majakka voi oman sijaintisolmunsa lisäksi valaista myös kaikki solmut, joiden etäisyys sijaintisolmusta on enintään $k$.

Kilpaohjelmoijana Little Y pohti luonnollisesti kysymystä: mikä on pienin määrä majakoita, jotka on sijoitettava, jotta kaikki solmut tulevat varmasti valaistuiksi?

Syöte

Tässä tehtävässä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^5$), joka ilmaisee testitapausten lukumäärän.

Jokaiselle testitapaukselle:

Ensimmäinen rivi sisältää kolme kokonaislukua $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$), jotka ilmaisevat kartan solmujen ja kaarten lukumäärän sekä suurimman etäisyyden, jonka majakka pystyy valaisemaan.

Seuraavat $m$ riviä sisältävät kukin kaksi kokonaislukua $u, v$ ($1 \le u, v \le n, u \ne v$), jotka ilmaisevat kartan kaaren.

On taattu, että annettu suuntaamaton verkko on yhtenäinen eikä siinä ole moninkertaisia kaaria tai silmukoita, ja että jokainen kaari esiintyy korkeintaan yhdessä syklissä. Lisäksi lukujen $n$ ja $m$ kokonaissumma yli kaikkien testitapausten on enintään $2 \times 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi kokonaisluku, joka ilmaisee sijoitettavien majakoiden vähimmäismäärän.

Esimerkki

Syöte

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

Tuloste

2
2
1

Huomautus

Ensimmäisessä testitapauksessa kaksi majakkaa voidaan sijoittaa solmuihin 1 ja 4.

Toisessa testitapauksessa kaksi majakkaa voidaan sijoittaa solmuihin 2 ja 5.

Kolmannessa testitapauksessa yksi kelvollinen ratkaisu on sijoittaa majakka solmuun 2. Voidaan todistaa, että tämä on ainoa ratkaisu, joka täyttää majakoiden vähimmäismäärän ehdon.