존경받는 교수인 Panda는 국제 대학생 프로그래밍 학술대회(International Collegiate Programming Conference)에 $n$편의 논문을 제출했습니다. 각 논문은 $m$명의 익명 심사위원에 의해 독립적으로 심사되며 점수를 부여받습니다.

심사 결과는 일곱 가지 등급으로 나뉘며, 각각 다음 점수에 대응합니다:

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

논문의 총점(모든 $m$명의 심사위원 점수의 합)이 기준치 $k$ 이상이면 해당 논문은 채택(Accept)되고, 그렇지 않으면 기각(Reject)됩니다.

심사위원들이 점수를 제출한 후에는 반론(rebuttal) 단계가 진행됩니다. Panda는 이 단계에서 서로 다른 논문을 최대 $b$편까지 선택할 수 있습니다. 반론은 선택된 논문에 대한 심사위원들의 평가를 개선하기 위한 변론입니다. 하지만 심사위원들마다 반응이 달라 점수가 다음과 같이 변합니다:

• 높은 점수($1$ 이상)를 주었던 심사위원들은 반론에 부정적으로 반응하여, 점수가 한 단계 낮아집니다(예: $3$은 $2$가 되고, $1$은 $0$이 됩니다).
• 낮은 점수($0$ 이하)를 주었던 심사위원들은 반론에 긍정적으로 반응하여, 점수가 한 단계 높아집니다(예: $-3$은 $-2$가 되고, $0$은 $1$이 됩니다).

Panda는 모든 반론이 반영된 후 최종적으로 채택되는 논문의 수를 최대화하기 위해 반론을 진행할 논문을 최대 $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$는 반론을 위해 선택할 수 있는 최대 논문 수입니다.

다음 $n$개의 줄 중 $i$번째 줄에는 공백으로 구분된 $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