Panda hat eine eindimensionale Achse, auf deren nichtnegativer Seite $n$ Segmente liegen. Der linke Endpunkt des $i$-ten Segments ist $l_i$. Jedes Segment hat dieselbe Länge $L$. Das bedeutet, dass das $i$-te Segment das Intervall $[l_i, l_i + L - 1]$ (einschließlich der Randpunkte) abdeckt.

Nun möchte Panda, dass Sie die maximale Anzahl ganzzahliger Punkte auf der nichtnegativen Seite der Achse bestimmen, die nach dem Verschieben von höchstens einem Segment genau $k$-mal abgedeckt werden können. Konkret dürfen Sie höchstens ein Segment auswählen und seinen linken Endpunkt auf eine beliebige nichtnegative ganze Zahl (ohne obere Schranke) ändern. Die Länge des Segments, $L$, bleibt unverändert.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 2 \times 10^5$), die Anzahl der Testfälle.

Für jeden Testfall enthält die erste Zeile drei positive ganze Zahlen $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$). $n$ ist die Gesamtzahl der Segmente, $L$ ist die feste Länge jedes Segments und $k$ ist die geforderte Abdeckungsanzahl.

Die zweite Zeile enthält $n$ nichtnegative ganze Zahlen. Die $i$-te ganze Zahl ist $l_i$ ($0 \le l_i \le 2 \times n$) und gibt den linken Endpunkt des $i$-ten Segments an.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $2 \times 10^5$ nicht überschreitet.

Ausgabe

Geben Sie für jeden Testfall eine Zeile mit einer einzigen ganzen Zahl aus, die die maximale Anzahl ganzzahliger Punkte bezeichnet, welche nach dem Verschieben von höchstens einem Segment genau $k$-mal abgedeckt werden können.

Beispiele

Eingabe 1

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

Ausgabe 1

6
3
0

Hinweis

Im ersten Testfall des Beispiels lauten die drei Segmente anfangs $[2, 3]$, $[6, 7]$ und $[2, 3]$. Sie können den linken Endpunkt des dritten Segments auf $114514$ ändern. Nach diesem Zug lauten die Segmente $[2, 3]$, $[6, 7]$ und $[114514, 114515]$. Dies führt zu $6$ ganzzahligen Punkten, die genau einmal abgedeckt sind, was dem erreichbaren Maximum entspricht.

Im zweiten Testfall können Sie den linken Endpunkt des ersten Segments auf $3$ verschieben, um die Anzahl der ganzzahligen Punkte, die genau zweimal abgedeckt werden, zu maximieren.