לפנדה יש ציר חד-ממדי שעל הצד האי-שלילי שלו מונחים $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$ כדי למקסם את מספר הנקודות השלמות המכוסות בדיוק פעמיים.