يزور Little 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}$. بالإضافة إلى ذلك، تُسمى مجموعة الحواف التي تصل جميع العقد بالترتيب على الدورة مجموعة حواف الدورة، وتُعد دورتان مختلفتين إذا وفقط إذا كانت مجموعتا حوافهما مختلفتين. ومع مواصلة Little Y لزيارته، اكتشف خاصية مميزة: كل حافة في البيان تظهر في دورة واحدة على الأكثر.

حاليًا، لا يوجد نظام إضاءة في الحديقة، لذلك عندما يحل الليل ستغرق الحديقة في ظلام دامس. لحسن الحظ، يستعد الموظفون لوضع منارات عند بعض العقد على الخريطة. تُعرَّف المسافة بين عقدتين في البيان بأنها أقل عدد من الحواف التي يجب عبورها للوصول من إحدى العقدتين إلى الأخرى. وبالتالي، فإن كل منارة، بالإضافة إلى إضاءة العقدة الموضوعة فيها، يمكنها أيضًا إضاءة جميع العقد التي لا تزيد مسافتها عن عقدة المنارة على $k$.

بصفته متسابقًا في البرمجة التنافسية، فكّر Little 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. يمكن إثبات أن هذا هو الحل الوحيد الذي يحقق شرط أقل عدد من المنارات.