ZZZZSGW is a cute hamster living in a beautiful city named WWW. However, the COVID-19 spread like a wild fire in his city, many people infected. With great grief and motivation, he really wants to do something for his hometown. Therefore he applied for the volunteer of his community to help his neighbors.
There are 
candidates and the voluntary team only needs several volunteers in total. To ensure the quality of the team, they decided to hold an election to pick out the volunteers. Every resident has to nominate exactly 
candidates and mustn't give more than one nomination to each candidate. (of course one can save one of the nominations for himself/herself). The candidates then will be ranked by the nominations they get in descending order, if there are candidates have the same number of nominations, they will be ranked by their names in lexicographically increasing order.
It's evident that the name ZZZZSGW won't take much chance, so when he has the same nominations with others, you can just suppose that he will always be the last! What's worse, the order to nominate is also according to the names, which means that this poor guy will also be the last one to make his decision among the residents!
However, as each coin has two sides, the last to make decision also means the one who knows everything ------ since everyone can see the current result when making nominations! Now it's ZZZZSGW's turn, he knows the current result and the final result only depends on his own decision. But he is too nervous to make a clear judgment! Can you help him to get the highest place under this situation?
输入描述:
The input consists of several test cases. The first line of the input is an integer 
, the number of the test cases.
For each test case, the first line will be two integers 
. The number of candidates and the number of nominations that each resident can make.
The next line will be integers 
separated by spaces, which are the current number nominations of each candidate. The first integer always refers to the nominations of ZZZZSGW.
For each test case, 
, 
. And there is 
for all test cases.
输出描述:
For each test case, output a single integer 
in a line, which is the best place ZZZZSGW can get after his turn.
示例1
输入
复制
2
5 3
5 1 2 6 7
5 3
5 1 2 5 7
备注:
There are more hidden rules in the election than you think, so don't be surprised that the sum of nominations can't be divided by . (Well, such hidden rules won't take effect on ZZZZSGW's turn, please don't worry.)