Panda, un profesor muy respetado, ha enviado $n$ artículos a la International Collegiate Programming Conference. Cada artículo es evaluado de forma independiente por $m$ revisores anónimos que le otorgan una puntuación.

Las revisiones tienen siete niveles, que corresponden a las siguientes puntuaciones:

• Strong Reject: $-3$
• Reject: $-2$
• Weak Reject: $-1$
• Borderline: $0$
• Weak Accept: $1$
• Accept: $2$
• Strong Accept: $3$

Un artículo es aceptado si su puntuación total (la suma de las puntuaciones de los $m$ revisores) es mayor o igual que un umbral $k$; de lo contrario, es rechazado.

Después de que los revisores envían sus puntuaciones, hay una fase de réplica (rebuttal). Panda puede seleccionar un máximo de $b$ artículos distintos durante esta fase. Una réplica es un argumento destinado a mejorar las evaluaciones de los revisores para un artículo seleccionado. Sin embargo, los revisores reaccionan de manera diferente, lo que lleva a estos cambios de puntuación:

• Los revisores que dieron una puntuación alta ($1$ o superior) reaccionarán negativamente a la réplica; su puntuación disminuye en un nivel (por ejemplo, $3$ pasa a ser $2$, $1$ pasa a ser $0$).
• Los revisores que dieron una puntuación baja ($0$ o inferior) reaccionarán positivamente a la réplica; su puntuación aumenta en un nivel (por ejemplo, $-3$ pasa a ser $-2$, $0$ pasa a ser $1$).

Panda quiere seleccionar estratégicamente a lo sumo $b$ artículos para presentar una réplica con el fin de maximizar el número final de artículos aceptados después de aplicar todas las réplicas.

Entrada

La primera línea contiene un único entero $T$ ($1 \le T \le 1000$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene cuatro enteros $n, m, k, b$ ($1 \le n \le 10^5$, $1 \le m \le 10$, $-30 \le k \le 30$, $0 \le b \le n$). $n$ es el número de artículos, $m$ es el número de revisores por artículo, $k$ es el umbral de puntuación para la aceptación y $b$ es el número máximo de artículos que se pueden seleccionar para una réplica.

La $i$-ésima de las siguientes $n$ líneas contiene $m$ enteros separados por espacios $s_{ij}$ ($-3 \le s_{ij} \le 3$), que representan las puntuaciones iniciales otorgadas por el $j$-ésimo revisor para el $i$-ésimo artículo.

Se garantiza que $\sum n \le 2 \cdot 10^5$ en todos los casos de prueba.

Salida

Para cada caso de prueba, imprime un entero en una línea, indicando el número máximo de artículos que posiblemente pueden ser aceptados.

Ejemplos

Entrada 1

2
5 3 2 1
-3 0 3
2 -2 -1
1 1 1
0 0 0
-1 -1 -1
3 2 -1 1
-1 -2
-3 -3
1 -3

Salida 1

2
1