Panda, un professore molto stimato, ha inviato $n$ articoli alla International Collegiate Programming Conference. Ogni articolo viene valutato in modo indipendente da $m$ revisori anonimi che gli assegnano un punteggio.

Le revisioni hanno sette livelli, che corrispondono ai seguenti punteggi:

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

Un articolo viene accettato se il suo punteggio totale (la somma di tutti gli $m$ punteggi dei revisori) è maggiore o uguale a una soglia $k$; altrimenti viene rifiutato.

Dopo che i revisori hanno inviato i loro punteggi, c'è una fase di replica (rebuttal). Panda può selezionare al massimo $b$ articoli distinti durante questa fase. Una replica è un'argomentazione volta a migliorare le valutazioni dei revisori per un articolo selezionato. Tuttavia, i revisori reagiscono in modo diverso, portando a queste variazioni di punteggio:

• I revisori che hanno dato un punteggio alto ($1$ o superiore) reagiranno negativamente alla replica; il loro punteggio diminuisce di un livello (ad es. $3$ diventa $2$, $1$ diventa $0$).
• I revisori che hanno dato un punteggio basso ($0$ o inferiore) reagiranno positivamente alla replica; il loro punteggio aumenta di un livello (ad es. $-3$ diventa $-2$, $0$ diventa $1$).

Panda vuole selezionare strategicamente al più $b$ articoli per una replica al fine di massimizzare il numero finale di articoli accettati dopo che tutte le repliche sono state applicate.

Input

La prima riga contiene un singolo intero $T$ ($1 \le T \le 1000$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga contiene quattro interi $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$ è il numero di articoli, $m$ è il numero di revisori per articolo, $k$ è la soglia di punteggio per l'accettazione e $b$ è il numero massimo di articoli che possono essere selezionati per una replica.

La $i$-esima delle successive $n$ righe contiene $m$ interi separati da spazi $s_{ij}$ ($-3 \le s_{ij} \le 3$), che rappresentano i punteggi iniziali assegnati dal $j$-esimo revisore per l'$i$-esimo articolo.

È garantito che $\sum n \le 2 \cdot 10^5$ su tutti i casi di test.

Output

Per ogni caso di test, stampa un intero su una riga, che indica il numero massimo di articoli che possono essere accettati.

Esempi

Input 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

Output 1

2
1