Panda, niezwykle szanowany profesor, zgłosił $n$ artykułów na konferencję International Collegiate Programming Conference. Każdy artykuł jest oceniany niezależnie przez $m$ anonimowych recenzentów, którzy przyznają mu ocenę punktową.

Recenzje mają siedem poziomów, którym odpowiadają następujące oceny:

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

Artykuł zostaje zaakceptowany, jeśli jego łączny wynik (suma ocen wszystkich $m$ recenzentów) jest większy lub równy progowi $k$; w przeciwnym razie zostaje odrzucony.

Po przesłaniu ocen przez recenzentów następuje faza odpowiedzi na recenzje (rebuttal). W tej fazie Panda może wybrać maksymalnie $b$ różnych artykułów. Odpowiedź (rebuttal) to argumentacja mająca na celu poprawę ocen recenzentów dla wybranego artykułu. Recenzenci reagują jednak różnie, co prowadzi do następujących zmian ocen:

• Recenzenci, którzy wystawili wysoką ocenę ($1$ lub wyższą), zareagują negatywnie na odpowiedź; ich ocena zmniejsza się o jeden poziom (np. $3$ zmienia się na $2$, a $1$ zmienia się na $0$).
• Recenzenci, którzy wystawili niską ocenę ($0$ lub niższą), zareagują pozytywnie na odpowiedź; ich ocena zwiększa się o jeden poziom (np. $-3$ zmienia się na $-2$, a $0$ zmienia się na $1$).

Panda chce strategicznie wybrać co najwyżej $b$ artykułów do złożenia odpowiedzi, aby zmaksymalizować końcową liczbę zaakceptowanych artykułów po uwzględnieniu wszystkich odpowiedzi.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 1000$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera cztery liczby całkowite $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$ to liczba artykułów, $m$ to liczba recenzentów przypadających na każdy artykuł, $k$ to próg punktowy akceptacji, a $b$ to maksymalna liczba artykułów, które można wybrać do odpowiedzi.

$i$-ty z kolejnych $n$ wierszy zawiera $m$ oddzielonych spacjami liczb całkowitych $s_{ij}$ ($-3 \le s_{ij} \le 3$), reprezentujących początkowe oceny wystawione przez $j$-tego recenzenta dla $i$-tego artykułu.

Gwarantowane jest, że $\sum n \le 2 \cdot 10^5$ po wszystkich przypadkach testowych.

Wyjście

Dla każdego przypadku testowego wypisz w jednym wierszu jedną liczbę całkowitą, oznaczającą maksymalną liczbę artykułów, które mogą zostać zaakceptowane.

Przykład

Wejście 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

Wyjście 1

2
1