Панда, глубокоуважаемый профессор, отправил $n$ статей на конференцию International Collegiate Programming Conference. Каждая статья независимо оценивается $m$ анонимными рецензентами, которые выставляют ей балл.

Рецензии имеют семь уровней, которым соответствуют следующие баллы:

• 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