Little Y visite un parc. La carte de ce parc peut être représentée par un graphe simple non orienté et connexe contenant $n$ nœuds et $m$ arêtes. Pour aider les visiteurs à planifier leurs itinéraires, il existe plusieurs cycles sur la carte ; chaque cycle peut être représenté par une séquence de nœuds distincts $e_1, e_2, \dots, e_l$, où $l \ge 3$, et pour tout $1 \le i \le l$, il existe une arête dans le graphe reliant $e_i$ et $e_{(i \bmod l)+1}$. De plus, l'ensemble des arêtes reliant tous les nœuds dans l'ordre sur le cycle est appelé l'ensemble d'arêtes du cycle, et deux cycles sont considérés comme différents si et seulement si leurs ensembles d'arêtes sont différents. En poursuivant sa visite, Little Y a découvert une propriété : chaque arête du graphe apparaît dans au plus un cycle.

Actuellement, il n'y a pas de système d'éclairage dans le parc, de sorte qu'à la tombée de la nuit, le parc sera complètement plongé dans l'obscurité. Heureusement, le personnel se prépare à placer des phares sur certains nœuds de la carte. La distance entre deux nœuds du graphe est définie comme le nombre minimum d'arêtes qu'il faut parcourir pour atteindre un nœud depuis un autre. Par conséquent, chaque phare, en plus d'éclairer le nœud où il est placé, peut également éclairer tous les nœuds situés à une distance d'au plus $k$ de ce nœud.

En tant que participant à des concours de programmation compétitive, Little Y s'est naturellement posé une question : quel est le nombre minimum de phares qu'il faut placer pour garantir que tous les nœuds soient éclairés ?

Entrée

Ce problème contient plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^5$), représentant le nombre de cas de test.

Pour chaque cas de test :

La première ligne contient trois entiers $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$), représentant le nombre de nœuds et d'arêtes sur la carte, ainsi que la distance maximale qu'un phare peut éclairer.

Les $m$ lignes suivantes contiennent chacune deux entiers $u, v$ ($1 \le u, v \le n, u \ne v$), représentant une arête sur la carte.

Il est garanti que le graphe non orienté donné est connexe, ne comporte ni arêtes multiples ni boucles, et que chaque arête apparaît dans au plus un cycle. De plus, la somme totale de $n$ et de $m$ sur l'ensemble des cas de test ne dépasse pas $2 \times 10^5$.

Sortie

Pour chaque cas de test, affichez un seul entier représentant le nombre minimum de phares qui doivent être placés.

Exemple

Entrée

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

Sortie

2
2
1

Note

Pour le premier cas de test, deux phares peuvent être placés respectivement aux nœuds 1 et 4.

Pour le deuxième cas de test, deux phares peuvent être placés respectivement aux nœuds 2 et 5.

Pour le troisième cas de test, une solution réalisable consiste à placer un phare au nœud 2. On peut prouver que c'est la seule solution satisfaisant la condition du nombre minimum de phares.