Little Y er að heimsækja garð. Kortið af þessum garði má tákna með óstefndu einföldu samanhangandi neti sem inniheldur $n$ hnúta og $m$ leggi. Til að hjálpa ferðalöngum að skipuleggja leiðir sínar eru nokkrar rásir (cycles) á kortinu; tákna má hverja rás með runu ólíkra hnúta $e_1, e_2, \dots, e_l$, þar sem $l \ge 3$, og fyrir öll $1 \le i \le l$ er til leggur í netinu sem tengir $e_i$ og $e_{(i \bmod l)+1}$. Að auki er mengi leggjanna sem tengja alla hnútana í röð á rásinni kallað leggjamengi rásarinnar, og tvær rásir teljast ólíkar þá og því aðeins að leggjamengi þeirra séu ólík. Þegar Little Y hélt heimsókninni áfram uppgötvaði hann eiginleika: hver leggur í netinu kemur fyrir í mesta lagi í einni rás.

Eins og er er ekkert ljósakerfi í garðinum, svo þegar dimmir verður garðurinn algerlega myrkvaður. Sem betur fer er starfsfólkið að undirbúa að setja upp vita á nokkrum hnútum á kortinu. Fjarlægðin milli tveggja hnúta á netinu er skilgreind sem lágmarksfjöldi leggja sem þarf að fara um til að komast frá öðrum hnútnum til hins. Því getur hver viti, auk þess að lýsa upp hnútinn sem hann stendur á, einnig lýst upp alla hnúta sem eru í fjarlægð sem er ekki meiri en $k$ frá staðsetningarhnútnum.

Sem keppandi í keppnisforritun velti Little Y eðlilega fyrir sér spurningu: hver er lágmarksfjöldi vita sem þarf að setja upp til að tryggja að allir hnútar séu upplýstir?

Inntak

Þetta verkefni inniheldur mörg prófunartilvik. Fyrsta lína inntaksins inniheldur heiltölu $T$ ($1 \le T \le 10^5$), sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur þrjár heiltölur $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$), sem tákna fjölda hnúta og leggja á kortinu, sem og hámarksfjarlægðina sem viti getur lýst upp.

Næstu $m$ línur innihalda hver um sig tvær heiltölur $u, v$ ($1 \le u, v \le n, u \ne v$), sem tákna legg á kortinu.

Tryggt er að gefna óstefnda netið sé samanhangandi og hafi hvorki margfalda leggi né sjálfslykkjur, og að hver leggur komi fyrir í mesta lagi í einni rás. Að auki fer heildarsumma $n$ og $m$ yfir öll prófunartilvik ekki yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina heiltölu sem táknar lágmarksfjölda vita sem þarf að setja upp.

Dæmi

Inntak

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

Úttak

2
2
1

Athugasemd

Fyrir fyrsta prófunartilvikið má setja tvo vita á hnút 1 og hnút 4.

Fyrir annað prófunartilvikið má setja tvo vita á hnút 2 og hnút 5.

Fyrir þriðja prófunartilvikið er ein möguleg lausn að setja vita á hnút 2. Sanna má að þetta sé eina lausnin sem uppfyllir skilyrðið um lágmarksfjölda vita.