Panda har en endimensionell axel med $n$ segment placerade på dess icke-negativa sida. Den vänstra ändpunkten för det $i$-te segmentet är $l_i$. Varje segment har samma längd, $L$. Detta innebär att det $i$-te segmentet täcker intervallet $[l_i, l_i + L - 1]$ (inklusive ändpunkterna).

Nu vill Panda att du hittar det maximala antalet heltalspunkter på den icke-negativa sidan av axeln som kan täckas exakt $k$ gånger efter att ha flyttat högst ett segment. Mer specifikt får du välja högst ett segment och ändra dess vänstra ändpunkt till ett godtyckligt icke-negativt heltal (utan övre gräns). Segmentets längd, $L$, förblir densamma.

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T \le 2 \times 10^5$), som anger antalet testfall.

För varje testfall innehåller den första raden tre positiva heltal $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$). $n$ är det totala antalet segment, $L$ är den fasta längden för varje segment och $k$ är det önskade antalet täckningar.

Den andra raden innehåller $n$ icke-negativa heltal. Det $i$-te heltalet är $l_i$ ($0 \le l_i \le 2 \times n$) och representerar den vänstra ändpunkten för det $i$-te segmentet.

Det garanteras att summan av $n$ över alla testfall inte överstiger $2 \times 10^5$.

Utdata

För varje testfall, skriv ut en rad med ett enda heltal som anger det maximala antalet heltalspunkter som kan täckas exakt $k$ gånger efter att ha flyttat högst ett segment.

Exempel

Indata 1

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

Utdata 1

6
3
0

Anmärkning

För det första testfallet i exemplet är de tre segmenten från början $[2, 3]$, $[6, 7]$ och $[2, 3]$. Du kan ändra det tredje segmentets vänstra ändpunkt till $114514$. Efter detta drag är segmenten $[2, 3]$, $[6, 7]$ och $[114514, 114515]$. Detta resulterar i $6$ heltalspunkter som täcks exakt en gång, vilket är det högsta möjliga.

För det andra testfallet kan du flytta det första segmentets vänstra ändpunkt till $3$ för att maximera antalet heltalspunkter som täcks exakt två gånger.