In a football championship, N teams are competing against each other on the league stage. The current number of points of each team are X1, X2, X3....XN. M days of league stage are remaining and on each day K teams win and each of the winning team's points is incremented by 1. Top B teams will qualify for the playoffs in the championship. Officials of the tournament want to how many teams have a non-zero probability of making it to the playoffs.
Note: If points of certain teams are equal, any of the teams can qualify for playoffs and each team has equal probability.
Input format
- The first line contains an integer T denoting the number of test cases. For each test case:
- The first line contains four space-separated integers N, M, K, and B.
- The second line contains N space-separated integers X1, X2, X3...XN.
Output format
Print T integers. For each test case:
- Print the number of teams that have a non-zero probability of making it to the playoffs.
Constraints
- 1≤T≤20000
- 1≤N≤200000
- 1≤M≤109
- 1≤B,K<N
- 1≤Xi≤109
- Sum of N over all test cases will not exceed 200000.
First test case: Only one team can make it to the playoffs, two days of league stage are left and 2 points on each day are to be gained. Every team has probablity to qualify for playoffs other than team with 1 point. Let us look at the scenarios:
Bold are those teams which we want to win:
Team with 4 points: [4,1,2,3] -> [5,2,2,3] -> [5,3,2,3]
Team with 1 points has no chance to qualify ( Zero probablity)
Team with 2 points: [4,1,2,3] -> [4,2,3,3] -> [4,3,4,3] (Any of the first or third team can qualify so probablity>0)
Team with 3 points: [4,1,2,3] -> [4,2,2,4] -> [4,3,2,5] 4th team has maximum points so they can be choosen in this case.
So all teams other than second have non-zero chance and also note that in case of ties you can qualify any team you want.
