Panda er með einvíðan ás og á ekki-neikvæðu hlið hans eru $n$ strik. Vinstri endapunktur $i$-ta striksins er $l_i$. Öll strikin hafa sömu lengd, $L$. Þetta þýðir að $i$-ta strikið þekur bilið $[l_i, l_i + L - 1]$ (með endapunktum).

Nú vill Panda að þú finnir mesta mögulega fjölda heiltölupunkta á ekki-neikvæðu hlið ássins sem hægt er að þekja nákvæmlega $k$ sinnum eftir að hafa fært í mesta lagi eitt strik. Nánar tiltekið máttu velja í mesta lagi eitt strik og breyta vinstri endapunkti þess í hvaða ekki-neikvæðu heiltölu sem er (án efri marka). Lengd striksins, $L$, helst óbreytt.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 2 \times 10^5$), sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan þrjár jákvæðar heiltölur $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$). $n$ er heildarfjöldi strika, $L$ er föst lengd hvers striks og $k$ er umbeðinn fjöldi þekkinga.

Önnur línan inniheldur $n$ ekki-neikvæðar heiltölur. $i$-ta heiltalan er $l_i$ ($0 \le l_i \le 2 \times n$) sem táknar vinstri endapunkt $i$-ta striksins.

Tryggt er að summa $n$ yfir öll prófunartilvik fer ekki yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu með einni heiltölu sem táknar mesta mögulega fjölda heiltölupunkta sem hægt er að þekja nákvæmlega $k$ sinnum eftir að hafa fært í mesta lagi eitt strik.

Dæmi

Inntak 1

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

Úttak 1

6
3
0

Athugasemd

Í fyrsta prófunartilvikinu í sýnidæminu eru strikin þrjú í upphafi $[2, 3]$, $[6, 7]$ og $[2, 3]$. Þú getur breytt vinstri endapunkti þriðja striksins í $114514$. Eftir þessa færslu eru strikin $[2, 3]$, $[6, 7]$ og $[114514, 114515]$. Þetta leiðir til þess að $6$ heiltölupunktar eru þaktir nákvæmlega einu sinni, sem er það mesta sem hægt er að ná.

Í öðru prófunartilvikinu geturðu fært vinstri endapunkt fyrsta striksins í $3$ til að hámarka fjölda heiltölupunkta sem eru þaktir nákvæmlega tvisvar.