Panda มีแกนหนึ่งมิติที่มีส่วนของเส้นตรง $n$ เส้นวางอยู่บนฝั่งไม่เป็นลบ จุดปลายด้านซ้ายของส่วนของเส้นตรงเส้นที่ $i$ คือ $l_i$ ส่วนของเส้นตรงทุกเส้นมีความยาวเท่ากันคือ $L$ นั่นหมายความว่าส่วนของเส้นตรงเส้นที่ $i$ จะครอบคลุมช่วง $[l_i, l_i + L - 1]$ (รวมจุดปลายทั้งสอง)

ตอนนี้ Panda ต้องการให้คุณหาจำนวนจุดพิกัดจำนวนเต็มที่มากที่สุดบนฝั่งไม่เป็นลบของแกน ที่สามารถถูกครอบคลุมพอดี $k$ ครั้ง หลังจากย้ายส่วนของเส้นตรงอย่างมากหนึ่งเส้น กล่าวคือ คุณได้รับอนุญาตให้เลือกส่วนของเส้นตรงอย่างมากหนึ่งเส้น แล้วเปลี่ยนจุดปลายด้านซ้ายของมันเป็นจำนวนเต็มไม่เป็นลบใด ๆ (โดยไม่มีขอบเขตบน) ทั้งนี้ความยาวของส่วนของเส้นตรง $L$ จะยังคงเดิม

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 2 \times 10^5$) แทนจำนวนกรณีทดสอบ

สำหรับแต่ละกรณีทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็มบวกสามจำนวนคือ $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$) โดยที่ $n$ คือจำนวนส่วนของเส้นตรงทั้งหมด $L$ คือความยาวคงที่ของส่วนของเส้นตรงแต่ละเส้น และ $k$ คือจำนวนครั้งของการครอบคลุมที่ต้องการ

บรรทัดที่สองประกอบด้วยจำนวนเต็มไม่เป็นลบ $n$ จำนวน จำนวนเต็มตัวที่ $i$ คือ $l_i$ ($0 \le l_i \le 2 \times n$) แทนจุดปลายด้านซ้ายของส่วนของเส้นตรงเส้นที่ $i$

รับประกันว่าผลรวมของ $n$ จากทุกกรณีทดสอบจะไม่เกิน $2 \times 10^5$

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้แสดงผลหนึ่งบรรทัดที่มีจำนวนเต็มเพียงจำนวนเดียว แทนจำนวนจุดพิกัดจำนวนเต็มที่มากที่สุดที่สามารถถูกครอบคลุมพอดี $k$ ครั้ง หลังจากย้ายส่วนของเส้นตรงอย่างมากหนึ่งเส้น

ตัวอย่าง

ข้อมูลนำเข้า 1

3
3 2 1
2 6 2
3 3 2
6 2 0
5 1 3
5 6 7 8 9

ข้อมูลส่งออก 1

6
3
0

หมายเหตุ

สำหรับกรณีทดสอบแรกในตัวอย่าง เริ่มต้นส่วนของเส้นตรงทั้งสามเส้นคือ $[2, 3]$, $[6, 7]$ และ $[2, 3]$ คุณสามารถเปลี่ยนจุดปลายด้านซ้ายของส่วนของเส้นตรงเส้นที่สามเป็น $114514$ หลังจากการย้ายนี้ ส่วนของเส้นตรงจะกลายเป็น $[2, 3]$, $[6, 7]$ และ $[114514, 114515]$ ส่งผลให้มีจุดพิกัดจำนวนเต็ม $6$ จุดที่ถูกครอบคลุมพอดีหนึ่งครั้ง ซึ่งเป็นค่ามากที่สุดที่เป็นไปได้

สำหรับกรณีทดสอบที่สอง คุณสามารถย้ายจุดปลายด้านซ้ายของส่วนของเส้นตรงเส้นแรกไปที่ $3$ เพื่อทำให้จำนวนจุดพิกัดจำนวนเต็มที่ถูกครอบคลุมพอดีสองครั้งมีค่ามากที่สุด