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. ניתן להוכיח שזהו הפתרון היחיד המקיים את תנאי המספר המינימלי של מגדלורים.