## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] MEX vs DIFF Codeforces Solution | Codeforces Problem Solution 2022

E. MEX vs DIFF
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $a$ of $n$ non-negative integers. In one operation you can change any number in the array to any other non-negative integer.

Let's define the cost of the array as $\mathrm{DIFF}\left(a\right)-\mathrm{MEX}\left(a\right)$, where $\mathrm{MEX}$ of a set of non-negative integers is the smallest non-negative integer not present in the set, and $\mathrm{DIFF}$ is the number of different numbers in the array.

For example, $\mathrm{MEX}\left(\left\{1,2,3\right\}\right)=0$$\mathrm{MEX}\left(\left\{0,1,2,4,5\right\}\right)=3$.

You should find the minimal cost of the array $a$ if you are allowed to make at most $k$ operations.

Input

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le {10}^{4}$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1\le n\le {10}^{5}$$0\le k\le {10}^{5}$) — the length of the array $a$ and the number of operations that you are allowed to make.

The second line of each test case contains $n$ integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($0\le {a}_{i}\le {10}^{9}$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed ${10}^{5}$.

Output

For each test case output a single integer — minimal cost that it is possible to get making at most $k$ operations.