CC 226 B

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void solve(){
    ll n, k; cin >> n >> k;
    vector<ll> a(n); for (ll &i : a) cin >> i;
    vector<ll> freq(n+1);      // freq array
    for (ll i = 1; i < n; i++) freq[a[i]]++;
    freq[a[0]] = 0;
    // {v1 -> c1, v2 -> c2....} we are not interested in v
    // sort ct, and change one by one [c0 <= c1 <= c2...]
    sort(freq.begin(), freq.end());
    ll distinct = 1;        // distinct ct [a0 always exist]
    for (ll i : freq){
        if (k >= i) k -= i;
        else distinct++;
    }
    cout << distinct << '\n';
}

int main() {
	// your code goes here
    ll t; cin >> t;
    while(t--) solve();
}

// TC -> O(N lg N) due to sorting
// SC -> O(N)