Panda, en högt respekterad professor, har skickat in $n$ artiklar till International Collegiate Programming Conference. Varje artikel bedöms oberoende av $m$ anonyma granskare som ger den en poäng.

Granskningarna har sju nivåer, vilka motsvarar följande poäng:

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

En artikel accepteras om dess totalpoäng (summan av alla $m$ granskares poäng) är större än eller lika med ett tröskelvärde $k$; annars refuseras den.

Efter att granskarna har lämnat in sina poäng följer en bemötandefas (rebuttal). Panda kan välja som mest $b$ olika artiklar under denna fas. Ett bemötande är en argumentation som syftar till att förbättra granskarnas bedömningar av en vald artikel. Granskarna reagerar dock olika, vilket leder till följande poängförändringar:

• Granskare som gav en hög poäng ($1$ eller högre) kommer att reagera negativt på bemötandet; deras poäng minskas med en nivå (t.ex. blir $3$ till $2$, och $1$ blir till $0$).
• Granskare som gav en låg poäng ($0$ eller lägre) kommer att reagera positivt på bemötandet; deras poäng ökas med en nivå (t.ex. blir $-3$ till $-2$, och $0$ blir till $1$).

Panda vill strategiskt välja högst $b$ artiklar för ett bemötande för att maximera det slutliga antalet accepterade artiklar efter att alla bemötanden har tillämpats.

Indata

Den första raden innehåller ett enda heltal $T$ ($1 \le T \le 1000$), som anger antalet testfall.

För varje testfall innehåller den första raden fyra heltal $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$ är antalet artiklar, $m$ är antalet granskare per artikel, $k$ är tröskelvärdet för att accepteras och $b$ är det maximala antalet artiklar som kan väljas för ett bemötande.

Den $i$-te av de följande $n$ raderna innehåller $m$ mellanslagsseparerade heltal $s_{ij}$ ($-3 \le s_{ij} \le 3$), som representerar de ursprungliga poängen som gavs av den $j$-te granskaren för den $i$-te artikeln.

Det garanteras att $\sum n \le 2 \cdot 10^5$ över alla testfall.

Utdata

För varje testfall, skriv ut ett heltal på en rad, som anger det maximala antalet artiklar som möjligen kan accepteras.

Exempel

Indata 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

Utdata 1

2
1