قام البروفيسور المرموق باندا بتقديم $n$ من الأوراق البحثية إلى المؤتمر الدولي للبرمجة الجامعية (International Collegiate Programming Conference). يتم تحكيم كل ورقة بحثية بشكل مستقل من قِبل $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$ هو الحد الأقصى لعدد الأوراق البحثية التي يمكن اختيارها للرد.

السطر الـ $i$ من الـ $n$ سطراً التالية يحتوي على $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