Little Y está visitando un parque. El mapa de este parque puede representarse mediante un grafo conexo simple no dirigido que contiene $n$ nodos y $m$ aristas. Para ayudar a los visitantes a planificar sus rutas, existen varios ciclos en el mapa; cada ciclo puede representarse mediante una secuencia de nodos distintos $e_1, e_2, \dots, e_l$, donde $l \ge 3$, y para todo $1 \le i \le l$, existe una arista en el grafo que conecta $e_i$ y $e_{(i \bmod l)+1}$. Además, el conjunto de aristas que conectan todos los nodos en orden en el ciclo se denomina conjunto de aristas del ciclo, y dos ciclos se consideran diferentes si y solo si sus conjuntos de aristas son diferentes. A medida que Little Y continuaba la visita, descubrió una propiedad: cada arista del grafo aparece a lo sumo en un ciclo.

Actualmente, no hay sistema de iluminación en el parque, por lo que cuando caiga la noche, el parque quedará completamente a oscuras. Afortunadamente, el personal se está preparando para colocar faros en algunos nodos del mapa. La distancia entre dos nodos del grafo se define como el número mínimo de aristas que deben recorrerse para llegar de un nodo a otro. Por lo tanto, cada faro, además de iluminar el nodo donde se coloca, también puede iluminar todos los nodos que se encuentren a una distancia no mayor que $k$ de dicho nodo.

Como concursante de programación competitiva, a Little Y naturalmente se le ocurrió una pregunta: ¿cuál es el número mínimo de faros que es necesario colocar para garantizar que todos los nodos queden iluminados?

Entrada

Este problema contiene múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 10^5$), que representa el número de casos de prueba.

Para cada caso de prueba:

La primera línea contiene tres enteros $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$), que representan el número de nodos y aristas en el mapa, así como la distancia máxima que puede iluminar un faro.

Las siguientes $m$ líneas contienen cada una dos enteros $u, v$ ($1 \le u, v \le n, u \ne v$), que representan una arista en el mapa.

Se garantiza que el grafo no dirigido dado es conexo y no tiene aristas múltiples ni bucles, y que cada arista aparece a lo sumo en un ciclo. Además, la suma total de $n$ y $m$ en todos los casos de prueba no supera $2 \times 10^5$.

Salida

Para cada caso de prueba, imprime un solo entero que represente el número mínimo de faros que es necesario colocar.

Ejemplo

Entrada

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

Salida

2
2
1

Nota

Para el primer caso de prueba, se pueden colocar dos faros en el nodo 1 y en el nodo 4 respectivamente.

Para el segundo caso de prueba, se pueden colocar dos faros en el nodo 2 y en el nodo 5 respectivamente.

Para el tercer caso de prueba, una solución factible es colocar un faro en el nodo 2. Se puede demostrar que esta es la única solución que cumple la condición de tener el número mínimo de faros.