פנדה, פרופסור מוערך מאוד, הגיש $n$ מאמרים לכנס התכנות הבינלאומי למכללות (International Collegiate Programming Conference). כל מאמר נשפט באופן בלתי תלוי על ידי $m$ סוקרים (reviewers) אנונימיים המעניקים לו ציון.

לביקורות יש שבע רמות, המתאימות לציונים הבאים:

• 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