Panda, en høyt respektert professor, har sendt inn $n$ artikler til International Collegiate Programming Conference. Hver artikkel vurderes uavhengig av $m$ anonyme fagfeller som gir den en poengsum.

Vurderingene har sju nivåer, som tilsvarer følgende poengsummer:

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

En artikkel blir akseptert hvis dens totale poengsum (summen av alle de $m$ fagfellenes poengsummer) er større enn eller lik en terskel $k$; ellers blir den avvist.

Etter at fagfellene har sendt inn poengsummene sine, følger en tilsvarfase (rebuttal). Panda kan velge maksimalt $b$ forskjellige artikler i løpet av denne fasen. Et tilsvar er et argument som tar sikte på å forbedre fagfellenes vurderinger av en valgt artikkel. Fagfellene reagerer imidlertid ulikt, noe som fører til disse poengendringene:

• Fagfeller som ga en høy poengsum ($1$ eller høyere), vil reagere negativt på tilsvaret; poengsummen deres reduseres med ett nivå (f.eks. blir $3$ til $2$, og $1$ blir til $0$).
• Fagfeller som ga en lav poengsum ($0$ eller lavere), vil reagere positivt på tilsvaret; poengsummen deres økes med ett nivå (f.eks. blir $-3$ til $-2$, og $0$ blir til $1$).

Panda ønsker å strategisk velge høyst $b$ artikler for tilsvar for å maksimere det endelige antallet aksepterte artikler etter at alle tilsvar er gjennomført.

Inndata

Den første linjen inneholder et enkelt heltall $T$ ($1 \le T \le 1000$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen fire heltall $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 antallet artikler, $m$ er antallet fagfeller per artikkel, $k$ er poengterskelen for aksept, og $b$ er det maksimale antallet artikler som kan velges for et tilsvar.

Den $i$-te av de neste $n$ linjene inneholder $m$ mellomromsatkilte heltall $s_{ij}$ ($-3 \le s_{ij} \le 3$), som representerer de opprinnelige poengsummene gitt av den $j$-te fagfellen for den $i$-te artikkelen.

Det er garantert at $\sum n \le 2 \cdot 10^5$ over alle testtilfeller.

Utdata

For hvert testtilfelle, skriv ut et heltall på én linje, som angir det maksimale antallet artikler som muligens kan bli akseptert.

Eksempler

Inndata 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