Panda ศาสตราจารย์ผู้เป็นที่เคารพนับถืออย่างสูง ได้ส่งบทความวิจัยจำนวน $n$ ฉบับไปยัง การประชุมวิชาการการเขียนโปรแกรมระดับอุดมศึกษานานาชาติ (International Collegiate Programming Conference) บทความแต่ละฉบับจะถูกตัดสินอย่างอิสระโดยผู้ทรงคุณวุฒิไม่ระบุนามจำนวน $m$ คน ซึ่งแต่ละคนจะให้คะแนน

ผลการประเมินมีเจ็ดระดับ ซึ่งตรงกับคะแนนดังนี้:

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

บทความจะได้รับการตอบรับ (accepted) หากคะแนนรวมของบทความนั้น (ผลรวมของคะแนนจากผู้ทรงคุณวุฒิทั้ง $m$ คน) มีค่ามากกว่าหรือเท่ากับเกณฑ์ $k$ มิฉะนั้นบทความจะถูกปฏิเสธ (rejected)

หลังจากที่ผู้ทรงคุณวุฒิส่งคะแนนแล้ว จะมีช่วงการชี้แจงโต้แย้ง (rebuttal phase) Panda สามารถเลือกบทความที่แตกต่างกันได้สูงสุด $b$ ฉบับในช่วงนี้ การชี้แจงโต้แย้งคือข้อโต้แย้งที่มุ่งปรับปรุงผลการประเมินของผู้ทรงคุณวุฒิสำหรับบทความที่เลือก อย่างไรก็ตาม ผู้ทรงคุณวุฒิแต่ละกลุ่มมีปฏิกิริยาแตกต่างกัน ส่งผลให้คะแนนเปลี่ยนแปลงไปดังนี้:

• ผู้ทรงคุณวุฒิที่ให้คะแนนสูง (ตั้งแต่ $1$ ขึ้นไป) จะมีปฏิกิริยาเชิงลบต่อการชี้แจงโต้แย้ง คะแนนของพวกเขาจะลดลงหนึ่งระดับ (เช่น $3$ กลายเป็น $2$, $1$ กลายเป็น $0$)
• ผู้ทรงคุณวุฒิที่ให้คะแนนต่ำ (ตั้งแต่ $0$ ลงมา) จะมีปฏิกิริยาเชิงบวกต่อการชี้แจงโต้แย้ง คะแนนของพวกเขาจะเพิ่มขึ้นหนึ่งระดับ (เช่น $-3$ กลายเป็น $-2$, $0$ กลายเป็น $1$)

Panda ต้องการเลือกบทความอย่างมีกลยุทธ์อย่างมาก $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