Маленький Y гуляє парком. Карту цього парку можна подати у вигляді неорієнтованого простого зв'язного графа, що містить $n$ вершин і $m$ ребер. Щоб допомогти відвідувачам планувати маршрути, на карті є декілька циклів; кожен цикл можна подати послідовністю різних вершин $e_1, e_2, \dots, e_l$, де $l \ge 3$, і для всіх $1 \le i \le l$ у графі існує ребро, що з'єднує $e_i$ та $e_{(i \bmod l)+1}$. Крім того, множина ребер, які послідовно з'єднують усі вершини циклу, називається множиною ребер циклу, а два цикли вважаються різними тоді й лише тоді, коли їхні множини ребер різні. Продовжуючи прогулянку, Маленький Y виявив властивість: кожне ребро графа входить щонайбільше до одного циклу.

Наразі в парку немає системи освітлення, тому з настанням ночі парк повністю занурюється в темряву. На щастя, працівники готуються встановити маяки в деяких вершинах на карті. Відстань між двома вершинами графа визначається як мінімальна кількість ребер, які потрібно пройти, щоб дістатися з однієї вершини до іншої. Отже, кожен маяк, окрім вершини, у якій його встановлено, може також освітлювати всі вершини, що знаходяться на відстані не більше ніж $k$ від неї.

Як учасник змагань зі спортивного програмування, Маленький Y природно замислився над питанням: яку мінімальну кількість маяків потрібно встановити, щоб гарантувати освітлення всіх вершин?

Вхідні дані

Ця задача містить декілька наборів вхідних даних. Перший рядок вхідних даних містить ціле число $T$ ($1 \le T \le 10^5$), що позначає кількість наборів вхідних даних.

Для кожного набору вхідних даних:

Перший рядок містить три цілі числа $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$), що позначають кількість вершин і ребер на карті, а також максимальну відстань, яку може освітлювати маяк.

Наступні $m$ рядків містять по два цілі числа $u, v$ ($1 \le u, v \le n, u \ne v$), що позначають ребро на карті.

Гарантується, що заданий неорієнтований граф є зв'язним, не має кратних ребер або петель, і кожне ребро входить щонайбільше до одного циклу. Крім того, загальна сума $n$ і $m$ за всіма наборами вхідних даних не перевищує $2 \times 10^5$.

Вихідні дані

Для кожного набору вхідних даних виведіть одне ціле число, що позначає мінімальну кількість маяків, які потрібно встановити.

Приклад

Вхідні дані

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

Вихідні дані

2
2
1

Примітка

Для першого набору вхідних даних можна встановити два маяки у вершинах 1 і 4 відповідно.

Для другого набору вхідних даних можна встановити два маяки у вершинах 2 і 5 відповідно.

Для третього набору вхідних даних одне з допустимих рішень — встановити маяк у вершині 2. Можна довести, що це єдине рішення, яке задовольняє умову мінімальної кількості маяків.