Little Y sta visitando un parco. La mappa di questo parco può essere rappresentata da un grafo semplice connesso non orientato contenente $n$ nodi e $m$ archi. Per aiutare i visitatori a pianificare i propri percorsi, nella mappa sono presenti diversi cicli; ogni ciclo può essere rappresentato da una sequenza di nodi distinti $e_1, e_2, \dots, e_l$, dove $l \ge 3$, e per ogni $1 \le i \le l$ esiste un arco nel grafo che collega $e_i$ ed $e_{(i \bmod l)+1}$. Inoltre, l'insieme degli archi che collegano in ordine tutti i nodi del ciclo è chiamato insieme degli archi del ciclo, e due cicli sono considerati diversi se e solo se i loro insiemi di archi sono diversi. Continuando la visita, Little Y ha scoperto una proprietà: ogni arco del grafo compare in al più un ciclo.

Attualmente nel parco non c'è alcun sistema di illuminazione, quindi al calar della notte il parco sarà completamente al buio. Fortunatamente, il personale si sta preparando a posizionare dei fari in alcuni nodi della mappa. La distanza tra due nodi del grafo è definita come il numero minimo di archi che devono essere attraversati per raggiungere un nodo dall'altro. Pertanto, ciascun faro, oltre a illuminare il nodo in cui è posizionato, può illuminare anche tutti i nodi che si trovano a una distanza non superiore a $k$ dal nodo di posizionamento.

Da concorrente di programmazione competitiva, Little Y si è posto naturalmente una domanda: qual è il numero minimo di fari che devono essere posizionati per garantire che tutti i nodi siano illuminati?

Input

Questo problema contiene più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^5$), che rappresenta il numero di casi di test.

Per ciascun caso di test:

La prima riga contiene tre interi $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$), che rappresentano il numero di nodi e di archi sulla mappa, nonché la distanza massima che un faro può illuminare.

Le successive $m$ righe contengono ciascuna due interi $u, v$ ($1 \le u, v \le n, u \ne v$), che rappresentano un arco sulla mappa.

È garantito che il grafo non orientato fornito sia connesso, non abbia archi multipli né cappi, e che ogni arco compaia in al più un ciclo. Inoltre, la somma totale di $n$ e $m$ su tutti i casi di test non supera $2 \times 10^5$.

Output

Per ciascun caso di test, stampa un singolo intero che rappresenta il numero minimo di fari che devono essere posizionati.

Esempio

Input

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

Output

2
2
1

Note

Per il primo caso di test, è possibile posizionare due fari rispettivamente nel nodo 1 e nel nodo 4.

Per il secondo caso di test, è possibile posizionare due fari rispettivamente nel nodo 2 e nel nodo 5.

Per il terzo caso di test, una soluzione ammissibile consiste nel posizionare un faro nel nodo 2. Si può dimostrare che questa è l'unica soluzione che soddisfa la condizione di avere il numero minimo di fari.