Panda, un professeur très respecté, a soumis $n$ articles à l'International Collegiate Programming Conference. Chaque article est évalué indépendamment par $m$ relecteurs anonymes qui lui attribuent chacun un score.

Les évaluations comportent sept niveaux, qui correspondent aux scores suivants :

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

Un article est accepté si son score total (la somme des scores des $m$ relecteurs) est supérieur ou égal à un seuil $k$ ; sinon, il est rejeté.

Après que les relecteurs ont soumis leurs scores, il y a une phase de réponse aux relecteurs (rebuttal). Panda peut sélectionner au maximum $b$ articles distincts durant cette phase. Une réponse est un argumentaire visant à améliorer les évaluations des relecteurs pour un article sélectionné. Cependant, les relecteurs réagissent différemment, ce qui entraîne les modifications de score suivantes :

• Les relecteurs ayant donné un score élevé ($1$ ou plus) réagiront négativement à la réponse ; leur score diminue d'un niveau (par exemple, $3$ devient $2$, $1$ devient $0$).
• Les relecteurs ayant donné un score faible ($0$ ou moins) réagiront positivement à la réponse ; leur score augmente d'un niveau (par exemple, $-3$ devient $-2$, $0$ devient $1$).

Panda souhaite sélectionner stratégiquement au plus $b$ articles pour une réponse afin de maximiser le nombre final d'articles acceptés une fois toutes les réponses appliquées.

Entrée

La première ligne contient un seul entier $T$ ($1 \le T \le 1000$), désignant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient quatre entiers $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$ est le nombre d'articles, $m$ est le nombre de relecteurs par article, $k$ est le seuil de score d'acceptation et $b$ est le nombre maximal d'articles pouvant être sélectionnés pour une réponse.

La $i$-ème des $n$ lignes suivantes contient $m$ entiers séparés par des espaces $s_{ij}$ ($-3 \le s_{ij} \le 3$), représentant les scores initiaux attribués par le $j$-ème relecteur au $i$-ème article.

Il est garanti que $\sum n \le 2 \cdot 10^5$ sur l'ensemble des cas de test.

Sortie

Pour chaque cas de test, affichez un entier sur une seule ligne, désignant le nombre maximal d'articles pouvant être acceptés.

Exemples

Entrée 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

Sortie 1

2
1