Panda ha un asse unidimensionale con $n$ segmenti posizionati sul suo semiasse non negativo. L'estremo sinistro dell'$i$-esimo segmento è $l_i$. Ogni segmento ha la stessa lunghezza, $L$. Ciò significa che l'$i$-esimo segmento copre l'intervallo $[l_i, l_i + L - 1]$ (estremi inclusi).

Ora, Panda vuole che tu trovi il massimo numero di punti interi sul semiasse non negativo dell'asse che possono essere coperti esattamente $k$ volte dopo aver spostato al più un segmento. Nello specifico, ti è consentito selezionare al più un segmento e modificare il suo estremo sinistro in qualsiasi intero non negativo (senza limite superiore). La lunghezza del segmento, $L$, rimane invariata.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 2 \times 10^5$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga contiene tre interi positivi $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$). $n$ è il numero totale di segmenti, $L$ è la lunghezza fissa di ogni segmento e $k$ è il numero di coperture richiesto.

La seconda riga contiene $n$ interi non negativi. L'$i$-esimo intero è $l_i$ ($0 \le l_i \le 2 \times n$) e rappresenta l'estremo sinistro dell'$i$-esimo segmento.

È garantito che la somma di $n$ su tutti i casi di test non supera $2 \times 10^5$.

Output

Per ogni caso di test, stampa una riga con un singolo intero, che indica il massimo numero di punti interi che possono essere coperti esattamente $k$ volte dopo aver spostato al più un segmento.

Esempi

Input 1

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

Output 1

6
3
0

Nota

Per il primo caso di test nell'esempio, inizialmente i tre segmenti sono $[2, 3]$, $[6, 7]$ e $[2, 3]$. Puoi cambiare l'estremo sinistro del terzo segmento in $114514$. Dopo questa mossa, i segmenti sono $[2, 3]$, $[6, 7]$ e $[114514, 114515]$. Ciò comporta $6$ punti interi coperti esattamente una volta, che è il massimo ottenibile.

Per il secondo caso di test, puoi spostare l'estremo sinistro del primo segmento in $3$ per massimizzare il numero di punti interi coperti esattamente due volte.