Little Y besucht einen Park. Die Karte dieses Parks kann durch einen ungerichteten, einfachen, zusammenhängenden Graphen mit $n$ Knoten und $m$ Kanten dargestellt werden. Um Besuchern bei der Routenplanung zu helfen, gibt es auf der Karte mehrere Kreise; jeder Kreis kann durch eine Folge paarweise verschiedener Knoten $e_1, e_2, \dots, e_l$ mit $l \ge 3$ dargestellt werden, wobei für alle $1 \le i \le l$ im Graphen eine Kante existiert, die $e_i$ und $e_{(i \bmod l)+1}$ verbindet. Darüber hinaus wird die Menge der Kanten, die alle Knoten des Kreises der Reihe nach verbinden, als Kantenmenge des Kreises bezeichnet, und zwei Kreise gelten genau dann als verschieden, wenn ihre Kantenmengen verschieden sind. Als Little Y seinen Besuch fortsetzte, entdeckte er eine Eigenschaft: Jede Kante im Graphen kommt in höchstens einem Kreis vor.

Derzeit gibt es im Park kein Beleuchtungssystem, sodass der Park bei Einbruch der Dunkelheit völlig im Dunkeln liegt. Glücklicherweise bereitet das Personal vor, an einigen Knoten auf der Karte Leuchttürme aufzustellen. Der Abstand zwischen zwei Knoten im Graphen ist definiert als die minimale Anzahl von Kanten, die durchlaufen werden müssen, um von einem Knoten zum anderen zu gelangen. Daher kann jeder Leuchtturm zusätzlich zu seinem eigenen Standortknoten auch alle Knoten beleuchten, deren Abstand vom Standortknoten höchstens $k$ beträgt.

Als Teilnehmer an Programmierwettbewerben stellte sich Little Y natürlich sofort die Frage: Was ist die minimale Anzahl von Leuchttürmen, die aufgestellt werden müssen, um sicherzustellen, dass alle Knoten beleuchtet sind?

Eingabe

Dieses Problem enthält mehrere Testfälle. Die erste Zeile der Eingabe enthält eine Ganzzahl $T$ ($1 \le T \le 10^5$), die die Anzahl der Testfälle darstellt.

Für jeden Testfall gilt:

Die erste Zeile enthält drei Ganzzahlen $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$), die die Anzahl der Knoten und Kanten auf der Karte sowie die maximale Entfernung darstellen, die ein Leuchtturm beleuchten kann.

Die nächsten $m$ Zeilen enthalten jeweils zwei Ganzzahlen $u, v$ ($1 \le u, v \le n, u \ne v$), die eine Kante auf der Karte darstellen.

Es wird garantiert, dass der gegebene ungerichtete Graph zusammenhängend ist, keine Mehrfachkanten oder Schleifen besitzt und jede Kante in höchstens einem Kreis vorkommt. Außerdem überschreitet die Gesamtsumme von $n$ und $m$ über alle Testfälle hinweg nicht $2 \times 10^5$.

Ausgabe

Gib für jeden Testfall eine einzelne Ganzzahl aus, die die minimale Anzahl von Leuchttürmen darstellt, die aufgestellt werden müssen.

Beispiel

Eingabe

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

Ausgabe

2
2
1

Hinweis

Für den ersten Testfall können zwei Leuchttürme an Knoten 1 bzw. Knoten 4 aufgestellt werden.

Für den zweiten Testfall können zwei Leuchttürme an Knoten 2 bzw. Knoten 5 aufgestellt werden.

Für den dritten Testfall besteht eine zulässige Lösung darin, einen Leuchtturm an Knoten 2 aufzustellen. Es lässt sich beweisen, dass dies die einzige Lösung ist, die die Bedingung einer minimalen Anzahl von Leuchttürmen erfüllt.