高名な教授である Panda は、国際大学対抗プログラミング会議（International Collegiate Programming Conference）に $n$ 本の論文を投稿しました。各論文は $m$ 人の匿名の査読者によって独立に審査され、それぞれスコアが付けられます。

査読評価には 7 つの段階があり、それぞれ次のスコアに対応しています：

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

ある論文の合計スコア（$m$ 人すべての査読者のスコアの総和）が閾値 $k$ 以上であればその論文は採択され、そうでなければ不採択となります。

査読者がスコアを提出した後、リバッタル（反論・回答）フェーズがあります。Panda はこのフェーズで最大 $b$ 本の異なる論文を選ぶことができます。リバッタルとは、選んだ論文に対する査読者の評価を改善することを目的とした主張です。しかし、査読者によって反応は異なり、スコアは次のように変化します：

• 高いスコア（$1$ 以上）を付けた査読者はリバッタルに対して否定的に反応し、スコアが 1 段階下がります（例：$3$ は $2$ に、$1$ は $0$ になります）。
• 低いスコア（$0$ 以下）を付けた査読者はリバッタルに対して肯定的に反応し、スコアが 1 段階上がります（例：$-3$ は $-2$ に、$0$ は $1$ になります）。

Panda は、すべてのリバッタルが適用された後に採択される論文の最終的な本数を最大化するために、リバッタルを行う論文を高々 $b$ 本、戦略的に選びたいと考えています。

入力

1 行目には、テストケースの個数を表す 1 つの整数 $T$（$1 \le T \le 1000$）が与えられます。

各テストケースについて、1 行目には 4 つの整数 $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 行に出力してください。

入出力例

入力 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