Busy Beaver es demasiado perezoso para escribir una historia interesante para este problema, así que simplemente te dio un enunciado formal.

Definimos una $M$-secuencia como una secuencia de enteros positivos, cada uno entre $1$ y $M$ inclusive.

Una $M$-secuencia se llama $K$-buena si la diferencia absoluta entre cualquier par de elementos adyacentes es como máximo $K$. Por ejemplo, $[1, 2, 3, 5, 5, 3, 2, 1]$ es $2$-buena y $2024$-buena, pero no $1$-buena. También consideramos que las $M$-secuencias de longitud $0$ o $1$ son $K$-buenas.

Dados los enteros positivos $N$, $M$, $K$, $L$, y una $M$-secuencia $a_1, \dots, a_N$ de longitud $N$, encuentra el número máximo posible de elementos en una $M$-secuencia $b$, tal que:

• $b$ tenga a $a$ como prefijo; y
• Toda subsecuencia $K$-buena de $b$ tenga como máximo $L$ elementos.

Recuerda que una subsecuencia de una secuencia se obtiene eliminando algunos elementos (posiblemente todos o ninguno) de una secuencia, sin reordenar los elementos restantes.

Entrada

Hay múltiples casos de prueba. La primera línea contiene un entero positivo $T$ ($1 \le T \le 2 \cdot 10^5$), el número de casos de prueba.

La primera línea de cada caso de prueba contiene cuatro enteros $N$, $M$, $K$, $L$ ($0 \le N \le 2 \cdot 10^5$, $1 \le M \le 10^9$, $0 \le K \le 10^9$, $1 \le L \le 10^9$).

La segunda línea de un caso de prueba contiene $a_1, \dots, a_N$ ($1 \le a_i \le M$). Si $N = 0$, entonces esta línea se omite.

Se garantiza que toda subsecuencia $K$-buena de $a$ tiene como máximo $L$ elementos. Además, la suma de $N$ sobre todos los casos de prueba no supera $4 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime una línea con el número máximo de elementos en $b$. Se puede demostrar que bajo las restricciones del problema, el máximo siempre existe y no supera $9 \cdot 10^{18}$.

Subtareas

• ($5$ puntos) $M \le K + 1$.
• ($5$ puntos) $K = 0$.
• ($10$ puntos) $N = 0$.
• ($15$ puntos) $N = 1$.
• ($30$ puntos) La suma de cada uno de $N$, $M$, $K$ y $L$ sobre todos los casos de prueba no supera $3000$.
• ($35$ puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

3
3 3 1 3
1 3 2
0 5 2 3
7 7 2 3
1 4 2 7 7 1 6

Salida 1

5
6
7

Nota

En el primer caso de prueba de ejemplo, una posible $M$-secuencia $b$ es $[1, 3, 2, 3, 1]$, cuyas subsecuencias $1$-buenas, tales como $[3, 2, 3]$ y $[3, 2, 1]$, tienen todas una longitud máxima de $L = 3$.

En el segundo caso de prueba de ejemplo, una posible $M$-secuencia $b$ es $[1, 1, 5, 4, 2, 5]$, cuyas subsecuencias $2$-buenas, tales como $[5, 4, 2]$ y $[1, 1, 2]$, tienen todas una longitud máxima de $L = 3$.

En el tercer caso de prueba de ejemplo, se puede demostrar que la única $b$ posible es $b = a$.