Panda, afar virtur prófessor, hefur sent $n$ greinar á ráðstefnuna International Collegiate Programming Conference. Hver grein er metin sjálfstætt af $m$ nafnlausum ritrýnum sem gefa henni einkunn.

Ritrýnin hefur sjö þrep sem samsvara eftirfarandi stigum:

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

Grein er samþykkt ef heildarstig hennar (summa stiga allra $m$ ritrýnanna) eru meiri en eða jöfn þröskuldi $k$; annars er henni hafnað.

Eftir að ritrýnarnir skila stigum sínum tekur við andmælafasi (rebuttal). Panda getur valið að hámarki $b$ ólíkar greinar í þessum fasa. Andmæli eru rökstuðningur sem miðar að því að bæta mat ritrýnanna á valinni grein. Ritrýnar bregðast hins vegar misjafnlega við, sem leiðir til eftirfarandi breytinga á stigum:

• Ritrýnar sem gáfu háa einkunn ($1$ eða hærri) bregðast neikvætt við andmælunum; einkunn þeirra lækkar um eitt þrep (t.d. verður $3$ að $2$ og $1$ verður að $0$).
• Ritrýnar sem gáfu lága einkunn ($0$ eða lægri) bregðast jákvætt við andmælunum; einkunn þeirra hækkar um eitt þrep (t.d. verður $-3$ að $-2$ og $0$ verður að $1$).

Panda vill velja með kænsku í mesta lagi $b$ greinar fyrir andmæli til að hámarka endanlegan fjölda samþykktra greina eftir að öllum andmælum hefur verið beitt.

Inntak

Fyrsta línan inniheldur eina heiltölu $T$ ($1 \le T \le 1000$), sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan fjórar heiltölur $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$ er fjöldi greina, $m$ er fjöldi ritrýna á hverja grein, $k$ er stigaþröskuldur fyrir samþykki og $b$ er hámarksfjöldi greina sem hægt er að velja fyrir andmæli.

$i$-ta línan af næstu $n$ línum inniheldur $m$ heiltölur aðskildar með bilum, $s_{ij}$ ($-3 \le s_{ij} \le 3$), sem tákna upphaflegu stigin sem $j$-ti ritrýnirinn gaf $i$-tu greininni.

Tryggt er að $\sum n \le 2 \cdot 10^5$ yfir öll prófunartilvik.

Úttak

Fyrir hvert prófunartilvik skaltu prenta heiltölu á eina línu sem táknar hámarksfjölda greina sem mögulega geta orðið samþykktar.

Dæmi

Inntak 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

Úttak 1

2
1