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 สามารถพิสูจน์ได้ว่านี่เป็นคำตอบเดียวที่สอดคล้องกับเงื่อนไขการมีจำนวนประภาคารน้อยที่สุด