Little Y zwiedza park. Mapę tego parku można przedstawić jako nieskierowany graf prosty i spójny zawierający $n$ wierzchołków oraz $m$ krawędzi. Aby pomóc turystom w planowaniu tras, na mapie znajduje się kilka cykli; każdy cykl można przedstawić jako ciąg parami różnych wierzchołków $e_1, e_2, \dots, e_l$, gdzie $l \ge 3$, oraz dla każdego $1 \le i \le l$ w grafie istnieje krawędź łącząca $e_i$ oraz $e_{(i \bmod l)+1}$. Ponadto zbiór krawędzi łączących kolejno wszystkie wierzchołki cyklu nazywamy zbiorem krawędzi tego cyklu, a dwa cykle uznajemy za różne wtedy i tylko wtedy, gdy ich zbiory krawędzi są różne. Kontynuując spacer, Little Y odkrył pewną własność: każda krawędź w grafie należy do co najwyżej jednego cyklu.

Obecnie w parku nie ma systemu oświetlenia, więc gdy zapadnie zmrok, park pogrąży się w całkowitej ciemności. Na szczęście obsługa przygotowuje się do ustawienia latarń w niektórych wierzchołkach na mapie. Odległość między dwoma wierzchołkami w grafie definiujemy jako minimalną liczbę krawędzi, które trzeba przejść, aby dotrzeć z jednego wierzchołka do drugiego. Wobec tego każda latarnia, oprócz oświetlania wierzchołka, w którym się znajduje, może również oświetlić wszystkie wierzchołki znajdujące się w odległości nie większej niż $k$ od tego wierzchołka.

Jako zawodnik programowania zespołowego, Little Y naturalnie zadał sobie pytanie: jaka jest minimalna liczba latarń, które należy ustawić, aby zapewnić oświetlenie wszystkich wierzchołków?

Wejście

To zadanie zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^5$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego:

Pierwszy wiersz zawiera trzy liczby całkowite $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$), oznaczające odpowiednio liczbę wierzchołków i krawędzi na mapie oraz maksymalną odległość, jaką może oświetlić latarnia.

Kolejne $m$ wierszy zawiera po dwie liczby całkowite $u, v$ ($1 \le u, v \le n, u \ne v$), oznaczające krawędź na mapie.

Gwarantowane jest, że dany graf nieskierowany jest spójny, nie zawiera krawędzi wielokrotnych ani pętli własnych, a każda krawędź występuje w co najwyżej jednym cyklu. Ponadto łączna suma $n$ oraz $m$ we wszystkich przypadkach testowych nie przekracza $2 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą oznaczającą minimalną liczbę latarń, które należy ustawić.

Przykład

Wejście

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

Wyjście

2
2
1

Uwaga

Dla pierwszego przypadku testowego można ustawić dwie latarnie odpowiednio w wierzchołkach 1 oraz 4.

Dla drugiego przypadku testowego można ustawić dwie latarnie odpowiednio w wierzchołkach 2 oraz 5.

Dla trzeciego przypadku testowego jednym z dopuszczalnych rozwiązań jest ustawienie latarni w wierzchołku 2. Można udowodnić, że jest to jedyne rozwiązanie spełniające warunek minimalnej liczby latarń.