Panda, ein hochangesehener Professor, hat $n$ wissenschaftliche Arbeiten bei der International Collegiate Programming Conference eingereicht. Jede Arbeit wird unabhängig von $m$ anonymen Gutachtern bewertet, die ihr jeweils eine Punktzahl geben.

Die Bewertungen haben sieben Stufen, die folgenden Punktzahlen entsprechen:

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

Eine Arbeit wird angenommen, wenn ihre Gesamtpunktzahl (die Summe aller $m$ Gutachterpunktzahlen) größer oder gleich einem Schwellenwert $k$ ist; andernfalls wird sie abgelehnt.

Nachdem die Gutachter ihre Punktzahlen abgegeben haben, gibt es eine Rebuttal-Phase (Gegendarstellung). Panda kann in dieser Phase maximal $b$ verschiedene Arbeiten auswählen. Ein Rebuttal ist eine Stellungnahme mit dem Ziel, die Bewertungen der Gutachter für eine ausgewählte Arbeit zu verbessern. Die Gutachter reagieren jedoch unterschiedlich, was zu folgenden Punktzahländerungen führt:

• Gutachter, die eine hohe Punktzahl ($1$ oder höher) vergeben haben, reagieren negativ auf das Rebuttal; ihre Punktzahl verringert sich um eine Stufe (z. B. wird $3$ zu $2$, $1$ wird zu $0$).
• Gutachter, die eine niedrige Punktzahl ($0$ oder niedriger) vergeben haben, reagieren positiv auf das Rebuttal; ihre Punktzahl erhöht sich um eine Stufe (z. B. wird $-3$ zu $-2$, $0$ wird zu $1$).

Panda möchte strategisch höchstens $b$ Arbeiten für ein Rebuttal auswählen, um die endgültige Anzahl der angenommenen Arbeiten nach Anwendung aller Rebuttals zu maximieren.

Eingabe

Die erste Zeile enthält eine einzelne ganze Zahl $T$ ($1 \le T \le 1000$), die Anzahl der Testfälle.

Für jeden Testfall enthält die erste Zeile vier ganze Zahlen $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$ ist die Anzahl der Arbeiten, $m$ ist die Anzahl der Gutachter pro Arbeit, $k$ ist der Schwellenwert für die Annahme und $b$ ist die maximale Anzahl von Arbeiten, die für ein Rebuttal ausgewählt werden können.

Die $i$-te der nächsten $n$ Zeilen enthält $m$ durch Leerzeichen getrennte ganze Zahlen $s_{ij}$ ($-3 \le s_{ij} \le 3$), welche die ursprünglichen Punktzahlen darstellen, die der $j$-te Gutachter für die $i$-te Arbeit vergeben hat.

Es wird garantiert, dass über alle Testfälle hinweg $\sum n \le 2 \cdot 10^5$ gilt.

Ausgabe

Gib für jeden Testfall in einer Zeile eine ganze Zahl aus, die die maximale Anzahl von Arbeiten angibt, die möglicherweise angenommen werden können.

Beispiele

Eingabe 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

Ausgabe 1

2
1