Pandalla on yksiulotteinen akseli, jonka ei-negatiiviselle puolelle on asetettu $n$ janaa. $i$-nnen janan vasen päätepiste on $l_i$. Jokaisella janalla on sama pituus, $L$. Tämä tarkoittaa, että $i$-s jana peittää suljetun välin $[l_i, l_i + L - 1]$.

Nyt Panda haluaa sinun etsivän suurimman mahdollisen määrän akselin ei-negatiivisella puolella olevia kokonaislukupisteitä, jotka voidaan peittää täsmälleen $k$ kertaa, kun siirretään enintään yhtä janaa. Tarkemmin sanoen saat valita enintään yhden janan ja muuttaa sen vasemman päätepisteen miksi tahansa ei-negatiiviseksi kokonaisluvuksi (ilman ylärajaa). Janan pituus $L$ pysyy samana.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 2 \times 10^5$), joka ilmoittaa testitapausten lukumäärän.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää kolme positiivista kokonaislukua $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$). $n$ on janojen kokonaismäärä, $L$ on jokaisen janan kiinteä pituus ja $k$ on vaadittu peittokertojen määrä.

Toinen rivi sisältää $n$ ei-negatiivista kokonaislukua. $i$-s kokonaisluku on $l_i$ ($0 \le l_i \le 2 \times n$), joka esittää $i$-nnen janan vasenta päätepistettä.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \times 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, jolla on yksi kokonaisluku: suurin mahdollinen määrä kokonaislukupisteitä, jotka voidaan peittää täsmälleen $k$ kertaa, kun siirretään enintään yhtä janaa.

Esimerkit

Syöte 1

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

Tuloste 1

6
3
0

Huomautus

Esimerkin ensimmäisessä testitapauksessa kolme janaa ovat aluksi $[2, 3]$, $[6, 7]$ ja $[2, 3]$. Voit muuttaa kolmannen janan vasemmaksi päätepisteeksi $114514$. Tämän siirron jälkeen janat ovat $[2, 3]$, $[6, 7]$ ja $[114514, 114515]$. Tällöin $6$ kokonaislukupistettä peittyy täsmälleen kerran, mikä on suurin saavutettavissa oleva määrä.

Toisessa testitapauksessa voit siirtää ensimmäisen janan vasemman päätepisteen kohtaan $3$ maksimoidaksesi täsmälleen kahdesti peittyvien kokonaislukupisteiden määrän.