Панда, вельмишановний професор, подав $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