Panda ma jednowymiarową oś, na której po nieujemnej stronie umieszczono $n$ odcinków. Lewym końcem $i$-tego odcinka jest $l_i$. Każdy odcinek ma tę samą długość $L$. Oznacza to, że $i$-ty odcinek pokrywa przedział $[l_i, l_i + L - 1]$ (włącznie z końcami).

Teraz Panda chce, abyś znalazł maksymalną liczbę punktów całkowitych po nieujemnej stronie osi, które mogą zostać pokryte dokładnie $k$ razy po przesunięciu co najwyżej jednego odcinka. Dokładniej, możesz wybrać co najwyżej jeden odcinek i zmienić jego lewy koniec na dowolną nieujemną liczbę całkowitą (bez górnego ograniczenia). Długość odcinka, $L$, pozostaje bez zmian.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 2 \times 10^5$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera trzy dodatnie liczby całkowite $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$). $n$ to łączna liczba odcinków, $L$ to stała długość każdego odcinka, a $k$ to wymagana krotność pokrycia.

Drugi wiersz zawiera $n$ nieujemnych liczb całkowitych. $i$-ta liczba całkowita to $l_i$ ($0 \le l_i \le 2 \times n$), reprezentująca lewy koniec $i$-tego odcinka.

Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $2 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz z pojedynczą liczbą całkowitą, oznaczającą maksymalną liczbę punktów całkowitych, które mogą zostać pokryte dokładnie $k$ razy po przesunięciu co najwyżej jednego odcinka.

Przykład

Wejście 1

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

Wyjście 1

6
3
0

Uwagi

W pierwszym przypadku testowym z przykładu początkowo trzy odcinki to $[2, 3]$, $[6, 7]$ oraz $[2, 3]$. Możesz zmienić lewy koniec trzeciego odcinka na $114514$. Po tym ruchu odcinki to $[2, 3]$, $[6, 7]$ oraz $[114514, 114515]$. Daje to $6$ punktów całkowitych pokrytych dokładnie jeden raz, co jest maksymalną możliwą wartością.

W drugim przypadku testowym możesz przesunąć lewy koniec pierwszego odcinka na $3$, aby zmaksymalizować liczbę punktów całkowitych pokrytych dokładnie dwa razy.