備受尊敬的 Panda 教授向國際大學生程式設計研討會（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）階段。在此階段，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$ 是最多可以選擇進行答辯的論文數量。

接下來的 $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