Panda possède un axe unidimensionnel avec $n$ segments placés sur sa partie positive ou nulle. L'extrémité gauche du $i$-ème segment est $l_i$. Chaque segment a la même longueur, $L$. Cela signifie que le $i$-ème segment couvre l'intervalle $[l_i, l_i + L - 1]$ (inclus).

Maintenant, Panda veut que vous trouviez le nombre maximal de points entiers sur la partie positive ou nulle de l'axe qui peuvent être couverts exactement $k$ fois après avoir déplacé au plus un segment. Plus précisément, vous êtes autorisé à sélectionner au plus un segment et à remplacer son extrémité gauche par n'importe quel entier positif ou nul (sans borne supérieure). La longueur du segment, $L$, reste la même.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 2 \times 10^5$), désignant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient trois entiers strictement positifs $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$). $n$ est le nombre total de segments, $L$ est la longueur fixe de chaque segment et $k$ est le nombre de couvertures requis.

La deuxième ligne contient $n$ entiers positifs ou nuls. Le $i$-ème entier est $l_i$ ($0 \le l_i \le 2 \times n$), représentant l'extrémité gauche du $i$-ème segment.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $2 \times 10^5$.

Sortie

Pour chaque cas de test, affichez une ligne contenant un seul entier, désignant le nombre maximal de points entiers pouvant être couverts exactement $k$ fois après avoir déplacé au plus un segment.

Exemples

Entrée 1

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

Sortie 1

6
3
0

Remarque

Pour le premier cas de test de l'exemple, initialement, les trois segments sont $[2, 3]$, $[6, 7]$ et $[2, 3]$. Vous pouvez changer l'extrémité gauche du troisième segment en $114514$. Après ce déplacement, les segments sont $[2, 3]$, $[6, 7]$ et $[114514, 114515]$. Cela donne $6$ points entiers couverts exactement une fois, ce qui est le maximum réalisable.

Pour le deuxième cas de test, vous pouvez déplacer l'extrémité gauche du premier segment en $3$ afin de maximiser le nombre de points entiers couverts exactement deux fois.