You own a race course where N different races are played on a day and the performance of the winner is recorded in an array A. The winner of the i′th race is A[i] horse. Being the owner, you are only interested in the performance of all the horses numbered from 1 to M. Let's denote the number of races won by the horses numbered from 1 to M by array B, where B[j] denotes the number of races won by horse j (1≤j≤M).
Let K denote the minimum value among all the elements of the array B. You are allowed to perform the following operations at most X times (maybe 0).
- Choose index i (1<=i<=N) change the value of A[i] i.e. the winner of race i.
You are given an integer X denoting the maximum number of operations you can perform. Find the maximum possible value of K after performing atmost X operations.
Note: There can be horses greater than M(M≤N) participating in the race, but we only care about the horses numbered from 1 to M.
Input Format
- The first line contains an integer T, which denotes the number of test cases.
- The first line of each test case contains three integers, denoting the value of N, M, and X respectively.
- The second line of each test case contains N space-separated integers, denoting the elements of array A.
Output Format
For each test case, print the maximum possible value of K.
Constraints
1≤T≤101≤N,M,X≤1051≤M,A[i]≤N
For test case 1: Initially, the array B is [2,4]. Now, we can perform at most two operations, so if we change A[2] to 1. The array B will be [3,4] and the minimum of array B i.e. K=3. There is no way to increase the value of K by further operations. So, the answer will be 3.
For test case 2: Here initially, the array B is [2,0,1] and we can perform at most 1 operations on the array A. So if we change A[4]=2. The array B will be [2,1,1] and the minimum of array B i.e. K=1. So, the answer will be 1.
For test case 3: Here initially, the array B is [1,2] and we can perform at most 2 operations on the array A. So if we change A[4]=1. The array B will be [2,2] and the minimum of array B i.e. K=2. There is no way to increase the value of K by further operations. So, the answer will be 2.
