备受尊敬的 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