Panda har en endimensjonal akse med $n$ segmenter plassert på dens ikke-negative side. Det venstre endepunktet til det $i$-te segmentet er $l_i$. Hvert segment har samme lengde, $L$. Dette betyr at det $i$-te segmentet dekker intervallet $[l_i, l_i + L - 1]$ (inkludert endepunktene).

Nå vil Panda at du skal finne det maksimale antallet heltallspunkter på den ikke-negative siden av aksen som kan dekkes nøyaktig $k$ ganger etter å ha flyttet høyst ett segment. Mer spesifikt har du lov til å velge høyst ett segment og endre dets venstre endepunkt til et hvilket som helst ikke-negativt heltall (uten øvre grense). Segmentets lengde, $L$, forblir den samme.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 2 \times 10^5$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen tre positive heltall $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$). $n$ er det totale antallet segmenter, $L$ er den faste lengden på hvert segment, og $k$ er det ønskede dekningsantallet.

Den andre linjen inneholder $n$ ikke-negative heltall. Det $i$-te heltallet er $l_i$ ($0 \le l_i \le 2 \times n$) og representerer det venstre endepunktet til det $i$-te segmentet.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $2 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én linje med ett enkelt heltall, som angir det maksimale antallet heltallspunkter som kan dekkes nøyaktig $k$ ganger etter å ha flyttet høyst ett segment.

Eksempler

Inndata 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

Merk

For det første testtilfellet i eksempelet er de tre segmentene til å begynne med $[2, 3]$, $[6, 7]$ og $[2, 3]$. Du kan endre det tredje segmentets venstre endepunkt til $114514$. Etter dette trekket er segmentene $[2, 3]$, $[6, 7]$ og $[114514, 114515]$. Dette resulterer i $6$ heltallspunkter som er dekket nøyaktig én gang, noe som er det maksimale som kan oppnås.

For det andre testtilfellet kan du flytte det første segmentets venstre endepunkt til $3$ for å maksimere antallet heltallspunkter som er dekket nøyaktig to ganger.