Little Y besøker en park. Kartet over denne parken kan representeres av en urettet enkel sammenhengende graf som inneholder $n$ noder og $m$ kanter. For å hjelpe reisende med å planlegge rutene sine, er det flere sykler på kartet; hver sykel kan representeres av en sekvens av ulike noder $e_1, e_2, \dots, e_l$, der $l \ge 3$, og for alle $1 \le i \le l$ finnes det en kant i grafen som forbinder $e_i$ og $e_{(i \bmod l)+1}$. I tillegg kalles mengden av kanter som forbinder alle nodene i rekkefølge på sykelen for sykelens kantmengde, og to sykler regnes som forskjellige hvis og bare hvis kantmengdene deres er forskjellige. Mens Little Y fortsatte besøket, oppdaget han en egenskap: hver kant i grafen forekommer i høyst én sykel.

For øyeblikket er det ikke noe belysningssystem i parken, så når natten faller på, vil parken bli helt mørk. Heldigvis forbereder de ansatte seg på å plassere fyrtårn ved noen noder på kartet. Avstanden mellom to noder i grafen er definert som det minste antallet kanter som må krysses for å nå den ene noden fra den andre. Derfor kan hvert fyrtårn, i tillegg til å lyse opp noden der det er plassert, også lyse opp alle noder som er i en avstand på høyst $k$ fra plasseringsnoden.

Som konkurranseprogrammerer tenkte Little Y naturlig nok på et spørsmål: hva er det minste antallet fyrtårn som må plasseres for å sikre at alle noder blir opplyst?

Inndata

Denne oppgaven inneholder flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10^5$), som representerer antallet testtilfeller.

For hvert testtilfelle:

Den første linjen inneholder tre heltall $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$), som representerer antallet noder og kanter på kartet, samt den maksimale avstanden et fyrtårn kan lyse opp.

De neste $m$ linjene inneholder hver to heltall $u, v$ ($1 \le u, v \le n, u \ne v$), som representerer en kant på kartet.

Det garanteres at den gitte urettede grafen er sammenhengende og ikke har multikanter eller løkker, og at hver kant forekommer i høyst én sykel. I tillegg overstiger ikke den totale summen av $n$ og $m$ over alle testtilfeller $2 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut et enkelt heltall som representerer det minste antallet fyrtårn som må plasseres.

Eksempel

Inndata

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

Utdata

2
2
1

Merk

For det første testtilfellet kan to fyrtårn plasseres ved henholdsvis node 1 og node 4.

For det andre testtilfellet kan to fyrtårn plasseres ved henholdsvis node 2 og node 5.

For det tredje testtilfellet er én mulig løsning å plassere et fyrtårn ved node 2. Det kan bevises at dette er den eneste løsningen som oppfyller betingelsen om å ha færrest mulig fyrtårn.