Panda, seorang profesor yang sangat dihormati, telah mengirimkan $n$ makalah ke International Collegiate Programming Conference. Setiap makalah dinilai secara independen oleh $m$ peninjau (reviewer) anonim yang memberikan sebuah skor.

Penilaian memiliki tujuh tingkatan, yang bersesuaian dengan skor berikut:

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

Sebuah makalah diterima jika total skornya (jumlah dari seluruh $m$ skor peninjau) lebih besar dari atau sama dengan ambang batas $k$; jika tidak, makalah tersebut ditolak.

Setelah para peninjau mengirimkan skor mereka, terdapat fase sanggahan (rebuttal). Panda dapat memilih maksimum $b$ makalah berbeda selama fase ini. Sanggahan adalah argumen yang bertujuan untuk memperbaiki evaluasi peninjau terhadap makalah yang dipilih. Namun, para peninjau bereaksi secara berbeda, yang menyebabkan perubahan skor sebagai berikut:

• Peninjau yang memberikan skor tinggi ($1$ atau lebih tinggi) akan bereaksi negatif terhadap sanggahan; skor mereka berkurang satu tingkat (misalnya, $3$ menjadi $2$, $1$ menjadi $0$).
• Peninjau yang memberikan skor rendah ($0$ atau lebih rendah) akan bereaksi positif terhadap sanggahan; skor mereka bertambah satu tingkat (misalnya, $-3$ menjadi $-2$, $0$ menjadi $1$).

Panda ingin memilih secara strategis paling banyak $b$ makalah untuk diajukan sanggahan guna memaksimalkan jumlah akhir makalah yang diterima setelah semua sanggahan diterapkan.

Masukan

Baris pertama berisi satu bilangan bulat $T$ ($1 \le T \le 1000$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi empat bilangan bulat $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$ adalah banyaknya makalah, $m$ adalah banyaknya peninjau per makalah, $k$ adalah ambang batas skor penerimaan, dan $b$ adalah banyaknya makalah maksimum yang dapat dipilih untuk sanggahan.

Baris ke-$i$ dari $n$ baris berikutnya berisi $m$ bilangan bulat yang dipisahkan spasi $s_{ij}$ ($-3 \le s_{ij} \le 3$), yang menyatakan skor awal yang diberikan oleh peninjau ke-$j$ untuk makalah ke-$i$.

Dijamin bahwa $\sum n \le 2 \cdot 10^5$ di seluruh kasus uji.

Keluaran

Untuk setiap kasus uji, keluarkan sebuah bilangan bulat dalam satu baris, yang menyatakan jumlah maksimum makalah yang mungkin dapat diterima.

Contoh

Masukan 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

Keluaran 1

2
1