يمتلك باندا محوراً أحادي البعد يحتوي على $n$ قطع موضوعة على جانبه غير السالب. نقطة البداية اليسرى للقطعة $i$ هي $l_i$. جميع القطع لها نفس الطول $L$. هذا يعني أن القطعة $i$ تغطي المجال $[l_i, l_i + L - 1]$ (شاملاً الطرفين).

الآن، يريد منك باندا إيجاد أكبر عدد من النقاط الصحيحة على الجانب غير السالب من المحور التي يمكن تغطيتها $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$ لتعظيم عدد النقاط الصحيحة المغطاة مرتين بالضبط.