Аса құрметті профессор Панда International Collegiate Programming Conference конференциясына $n$ ғылыми мақала жіберді. Әрбір мақаланы $m$ анонимді рецензент тәуелсіз түрде бағалап, оған ұпай береді.

Рецензиялардың жеті деңгейі бар, олар келесі ұпайларға сәйкес келеді:

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

Егер мақаланың жалпы ұпайы (барлық $m$ рецензент ұпайларының қосындысы) $k$ шегінен үлкен немесе оған тең болса, мақала қабылданады; әйтпесе ол қабылданбайды.

Рецензенттер өз ұпайларын жібергеннен кейін апелляция (rebuttal) кезеңі басталады. Осы кезеңде Панда әртүрлі ең көбі $b$ мақаланы таңдай алады. Апелляция — таңдалған мақала бойынша рецензенттердің бағасын жақсартуға бағытталған уәж. Алайда рецензенттер оған әртүрлі қарайды, бұл ұпайлардың келесідей өзгеруіне әкеледі:

• Жоғары ұпай ($1$ немесе одан жоғары) қойған рецензенттер апелляцияға теріс қарайды; олардың ұпайы бір деңгейге төмендейді (мысалы, $3$ мәні $2$-ге, ал $1$ мәні $0$-ге айналады).
• Төмен ұпай ($0$ немесе одан төмен) қойған рецензенттер апелляцияға оң қарайды; олардың ұпайы бір деңгейге жоғарылайды (мысалы, $-3$ мәні $-2$-ге, ал $0$ мәні $1$-ге айналады).

Панда барлық апелляциялар қолданылғаннан кейін қабылданатын мақалалардың қорытынды санын барынша көбейту үшін апелляцияға көп дегенде $b$ мақаланы стратегиялық түрде таңдағысы келеді.

Кіріс деректер

Бірінші жолда тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T \le 1000$) берілген.

Әрбір тест жағдайы үшін бірінші жолда төрт бүтін сан $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$ — мақалалар саны, $m$ — әр мақалаға шаққандағы рецензенттер саны, $k$ — қабылдау ұпайының шегі, ал $b$ — апелляция үшін таңдауға болатын мақалалардың ең көп саны.

Келесі $n$ жолдың $i$-шісінде бос орынмен бөлінген $m$ бүтін сан $s_{ij}$ ($-3 \le s_{ij} \le 3$) берілген, олар $j$-ші рецензенттің $i$-ші мақалаға берген бастапқы ұпайларын білдіреді.

Барлық тест жағдайлары бойынша $\sum n \le 2 \cdot 10^5$ екеніне кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін бір жолда қабылдануы мүмкін мақалалардың ең көп санын білдіретін бір бүтін сан шығарыңыз.

Мысалдар

Кіріс деректер 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

Шығыс деректер 1

2
1