Panda, a highly respected professor, has submitted $n$ papers to the International Collegiate Programming Conference. Each paper is judged independently by $m$ anonymous reviewers who give it a score.

Reviews have seven levels, which correspond to scores:

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

A paper is accepted if its total score (the sum of all $m$ reviewer scores) is greater than or equal to a threshold $k$; otherwise, it is rejected.

After the reviewers submit their scores, there is a rebuttal phase. Panda can select a maximum of $b$ distinct papers during this phase. A rebuttal is an argument aimed at improving the reviewers' evaluations for a selected paper. However, reviewers react differently, leading to these score changes:

• Reviewers who gave a high score ($1$ or higher) will react negatively to the rebuttal; their score is decreased by one level (e.g., $3$ becomes $2$, $1$ becomes $0$).
• Reviewers who gave a low score ($0$ or lower) will react positively to the rebuttal; their score is increased by one level (e.g., $-3$ becomes $-2$, $0$ becomes $1$).

Panda wants to strategically select at most $b$ papers for a rebuttal to maximize the final number of accepted papers after all rebuttals are applied.

Input

The first line contains a single integer $T$ ($1 \le T \le 1000$), denoting the number of test cases.

For each test case, the first line contains four integers $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$ is the number of papers, $m$ is the number of reviewers per paper, $k$ is the acceptance score threshold, and $b$ is the maximum number of papers that can be selected for a rebuttal.

The $i$-th of the next $n$ lines contains $m$ space-separated integers $s_{ij}$ ($-3 \le s_{ij} \le 3$), representing the initial scores given by the $j$-th reviewer for the $i$-th paper.

It is guaranteed that $\sum n \le 2 \cdot 10^5$ over all test cases.

Output

For each test case, output an integer in one line, denoting the maximum number of papers that can be possibly accepted.

Examples

Input 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

Output 1

2
1