C. Educational Round
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You wrote a contest where you competed against $$$n$$$ other participants, and you were given $$$p$$$ problems to solve.

You solved exactly $$$x$$$ problems. For each problem $$$i$$$, you know that it was solved by exactly $$$k_i$$$ of your competitors.

You do not know which participants solved which problems. Find the minimum possible number of participants who solved strictly more problems than you.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$p$$$, and $$$x$$$ ($$$1 \le n, p \le 10^6$$$, $$$0 \le x \le p$$$) — the number of your competitors, the number of problems, and the number of problems you solved.

The second line of each test case contains $$$p$$$ integers $$$k_1, k_2, \ldots, k_p$$$ ($$$0 \le k_i \le n$$$), where $$$k_i$$$ is the number of other competitors who solved problem $$$i$$$.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$p$$$ over all test cases do not exceed $$$10^6$$$.

Output

For each test case, output a single integer — the minimum possible number of participants who could have solved strictly more problems than you.

Example
Input
4
2 4 1
2 2 2 2
5 2 1
0 1
4 5 3
4 4 3 3 0
6 6 3
4 4 4 3 3 4
Output
2
0
2
2
Note

In the first test, both of your competitors solved all $$$4$$$ problems, but you solved just one, so you are definitely behind both of them.

In the fourth test case, you could have lost to $$$2$$$ competitors if they solved the following sets of problems:

  • 5:A.CDEF
  • 5:AB.DEF
  • 3:ABC...
  • 3:...DEF
  • 3:ABC...
  • 3:.BC..F

It can be shown that there is no more optimal solution.