Panda tiene un eje unidimensional con $n$ segmentos colocados en su lado no negativo. El extremo izquierdo del $i$-ésimo segmento es $l_i$. Todos los segmentos tienen la misma longitud, $L$. Esto significa que el $i$-ésimo segmento cubre el intervalo $[l_i, l_i + L - 1]$ (inclusive).

Ahora, Panda quiere que encuentres el número máximo de puntos enteros en el lado no negativo del eje que pueden ser cubiertos exactamente $k$ veces después de mover a lo sumo un segmento. Específicamente, se te permite seleccionar a lo sumo un segmento y cambiar su extremo izquierdo a cualquier entero no negativo (sin límite superior). La longitud del segmento, $L$, permanece igual.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 2 \times 10^5$), que denota el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene tres enteros positivos $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$). $n$ es el número total de segmentos, $L$ es la longitud fija de cada segmento y $k$ es la cantidad de coberturas requerida.

La segunda línea contiene $n$ enteros no negativos. El $i$-ésimo entero es $l_i$ ($0 \le l_i \le 2 \times n$), que representa el extremo izquierdo del $i$-ésimo segmento.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2 \times 10^5$.

Salida

Para cada caso de prueba, imprime una línea con un solo entero, que denote el número máximo de puntos enteros que pueden ser cubiertos exactamente $k$ veces después de mover a lo sumo un segmento.

Ejemplos

Entrada 1

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

Salida 1

6
3
0

Nota

Para el primer caso de prueba del ejemplo, inicialmente los tres segmentos son $[2, 3]$, $[6, 7]$ y $[2, 3]$. Puedes cambiar el extremo izquierdo del tercer segmento a $114514$. Después de este movimiento, los segmentos son $[2, 3]$, $[6, 7]$ y $[114514, 114515]$. Esto da como resultado $6$ puntos enteros cubiertos exactamente una vez, que es el máximo alcanzable.

Para el segundo caso de prueba, puedes mover el extremo izquierdo del primer segmento a $3$ para maximizar el número de puntos enteros cubiertos exactamente dos veces.