Read problems statements in [Mandarin Chinese], [Russian], and [Bengali] as well.

There are n chocolates, and you are given an array of n numbers where the i-th number A_{i} is the flavour type of the i-th chocolate. Sebrina wants to eat as many different types of chocolates as possible, but she also has to save at least x number of chocolates for her little brother. 

Find the maximum possible number of distinct flavour types Sebrina can have.

------ Input Format ------ 

The first line contains an integer T --- the number of test cases.
- The first line of each test case consists of two integers n, x - The number of chocolates Sabrina has and the number of chocolates she has to save for her brother, respectively.
- The second line contains n integers A_{1},\ldots, A_{n}, where the i-th chocolate has type A_{i}.

------ Output Format ------ 

For each test case, output a single integer denoting the maximum possible number of distinct chocolate flavours Sabrina can eat.

------ Constraints ------ 

$1≤T≤10$
$1 ≤x ≤ n ≤2 \cdot 10^{5}  $ 
$1 ≤A_{i} ≤10^{9}$
- Sum of $n$ over all test cases do not exceed $ 2 \cdot 10^{5}  $

----- Sample Input 1 ------ 
3

2 1

1 2

4 2

1 1 1 1

5 3

50 50 50 100 100
----- Sample Output 1 ------ 
1

1

2
----- explanation 1 ------ 
Test case $1$: In the first case, the maximum number of chocolates Sebrina can have is $1$ as she has to leave $1$ chocolate for her brother. Thus, the maximum number of distinct chocolates is also $1$.

Test case $2$: Sebrina has to leave $2$ chocolates for her brother. She can eat any $2$ chocolates. Since all the chocolates have the same flavor, it does not matter which chocolates she eats. The maximum number of distinct chocolates would be $1$.

Test case $3$: Sebrina needs to save $3$ chocolates for her brother. She can eat any $2$ chocolates. To maximize the number of distinct chocolates, she can eat chocolates $1$ and $5$ with flavors $50$ and $100$ respectively. Thus maximum number of distinct chocolates is $2$.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(num_choc, bro) = map(int, input().split())
	havable = num_choc - bro
	lit = set(map(int, input().split()))
	print(min(len(lit), havable))


from collections import Counter
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	flavour = [int(x) for x in input().split()]
	flavour = dict(Counter(flavour))
	print(min(a - b, len(flavour.keys())))


T = int(input())
for _ in range(T):
	(n, x) = map(int, input().split())
	A = list(map(int, input().split()))
	flavours = set(A)
	remaining_chocos = n - len(flavours)
	if remaining_chocos >= x:
		print(len(flavours))
	else:
		print(n - x)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	eat = n - x
	s = set(l)
	if len(s) > eat:
		print(eat)
	else:
		print(len(s))


T = int(input())
for i in range(T):
	(n, x) = map(int, input().split())
	L = set(map(int, input().split()))
	a = n - x
	print(min(len(L), a))


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	lst = list(map(int, input().split()))
	diff = set(lst)
	chocs = n - x
	if chocs >= len(diff):
		print(len(diff))
	else:
		print(chocs)


def main():
	T = int(input())
	while T > 0:
		count_chocolates()
		T -= 1

def count_chocolates():
	(n, x) = map(int, input().split())
	chocolates = list(map(int, input().split()))
	sabrina_count = n - x
	sabrina_chocolates = set(chocolates)
	total_chocolates = len(sabrina_chocolates)
	if total_chocolates == sabrina_count or total_chocolates == 0:
		print(total_chocolates)
	elif total_chocolates > sabrina_count:
		print(sabrina_count)
	else:
		print(total_chocolates)
main()


T = int(input())
for _ in range(T):
	(n, x) = (int(i) for i in input().split())
	A = [int(i) for i in input().split()]
	d = {}
	for Ai in A:
		if Ai not in d:
			d[Ai] = 1
		else:
			d[Ai] += 1
	l = list(d.values())
	if x <= n - len(l):
		print(len(l))
	else:
		print(-x + n)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	li = list(map(int, input().split()))
	dis = len(list(set(li)))
	if dis < n - x:
		print(dis)
	else:
		print(n - x)


a = int(input(''))
for i in range(a):
	(n, x) = [int(x) for x in input('').split()]
	t = [int(x) for x in input('').split()]
	k = list(t)
	g = set(k)
	d = len(g)
	if d <= n - x:
		print(d)
	else:
		print(n - x)


N = int(input())
for _ in range(N):
	(n, x) = map(int, input().split())
	chocolate = map(int, input().split())
	d = len(set(chocolate))
	best = min(n - x, d)
	print(best)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	s = n - x
	a = set(a)
	print(min(len(a), s))


for t in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	y = len(set(l))
	print(min(n - x, y))


from collections import Counter
for i in range(int(input())):
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = 0
	d = 0
	for j in Counter(b).values():
		if j != 1:
			c += j - 1
		d += 1
	if a[-1] > c:
		print(c + d - a[-1])
	else:
		print(d)


T = int(input())
for _ in range(0, T):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a = [*set(a)]
	f = len(a)
	print(min(f, n - x))


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(set(A))
	z = len(A) - len(B)
	if z >= x:
		print(len(B))
	else:
		print(len(B) - abs(z - x))


t = int(input())
while t != 0:
	(n, b) = map(int, input().split())
	l = list(map(int, input().split()))
	u = len(set(l))
	if n - u < b:
		u -= b - (n - u)
	print(u)
	t -= 1


T = int(input())
for i in range(T):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	diff = n - x
	count = set(arr)
	flav = len(count)
	if diff > flav:
		print(flav)
	elif diff == flav:
		print(flav)
	elif diff < flav:
		print(diff)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	c = len(set(a))
	b = n - x
	if c >= b:
		print(b)
	else:
		print(c)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	lst = list(map(int, input().split()))
	l1 = len(set(lst))
	l2 = len(lst) - l1
	k = len(lst) - x
	if k <= l1:
		print(k)
	else:
		print(l1)


T = int(input())
for _ in range(T):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	left = n - x
	s = set(l)
	if len(s) >= left:
		print(left)
	else:
		print(len(s))


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = set(arr)
	l = len(s)
	diff = n - x
	print(min(diff, l))


t = int(input())
for _ in range(t):
	(n, y) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	distinct = len(set(arr))
	left = n - y
	if distinct >= left:
		print(left)
	else:
		print(distinct)


try:
	for _ in range(int(input())):
		(n, x) = list(map(int, input().split()))
		l = list(map(int, input().split()))
		ll = list(set(l))
		print(min(len(l) - x, len(ll)))
except:
	pass


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	d = {}
	l = list(map(int, input().split()))
	for i in l:
		if i in d:
			d[i] = d[i] + 1
		else:
			d[i] = 1
	l = []
	for (i, j) in d.items():
		if x > 0:
			if j - 1 > 0:
				x = x - j + 1
		l.append(i)
	if x > 0:
		print(len(l) - x)
	else:
		print(len(l))


for _ in range(int(input())):
	(n, b) = map(int, input().split())
	l = len(set(map(int, input().split())))
	if l >= n - b:
		print(n - b)
	else:
		print(l)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l = len(list(set(l)))
	if l >= n - x:
		print(n - x)
	elif l < n - x:
		print(l)


t = int(input())
for a in range(t):
	(n, t) = map(int, input().rsplit())
	lst = list(map(int, input().rsplit()))
	slst = set(lst)
	d = len(slst)
	f = len(lst)
	di = f - d
	if di >= t:
		print(d)
	else:
		print(d - (t - di))


t = input()
for c in range(0, int(t)):
	(n, x) = input().split()
	a = input().split()
	arr = []
	srr = []
	for y in a:
		arr.append(int(y))
		srr.append(int(y))
	srr = set(srr)
	spare = len(arr) - len(srr)
	if spare == 0:
		print(len(arr) - int(x))
	else:
		spare = spare - int(x)
		if spare < 0:
			print(len(srr) + spare)
		else:
			print(len(srr))


t = int(input())
for _ in range(0, t):
	(n, x) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	j = 1
	k = l[0]
	for i in l[1:n]:
		if k != i:
			j += 1
			k = i
	y = n - x
	print(min(j, y))


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))[:n]
	a.sort()
	c = 1
	for i in range(n - 1):
		if a[i] != a[i + 1]:
			c += 1
	print(min(c, n - x))


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	b = len(set(a))
	print(min(b, n - x))


for i in range(int(input())):
	(n, x) = map(int, input().split())
	flav = list(map(int, input().split()))
	if n == x:
		print(0)
	elif len(set(flav)) + x <= n:
		print(len(set(flav)))
	else:
		print(n - x)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	sl = list(set(l))
	ns = len(sl)
	r = n - ns
	if r >= k:
		print(ns)
	else:
		print(n - k)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	s = set(l)
	d = a - b
	if len(s) < d:
		print(len(s))
	elif len(s) >= d:
		print(d)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = set(map(int, input().split()))
	if len(a) >= n - x:
		print(n - x)
	elif len(a) < n - x:
		print(len(a))


for _ in range(int(input())):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	serina_choc = n - x
	a.sort()
	counter = 0
	ans = 0
	for i in range(len(a)):
		if counter == serina_choc:
			break
		elif i > 0 and a[i] != a[i - 1]:
			ans += 1
			counter += 1
		elif i == 0 and len(a) > 0:
			ans = 1
			counter += 1
	print(ans)


tests = int(input())
for i in range(tests):
	(n, x) = map(int, input().split())
	unique_choco = len(set(map(int, input().split())))
	print(min(unique_choco, n - x))


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	print(min(len(set(map(int, input().split()))), n - x))


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	left = n - x
	flav = list(map(int, input().split()))
	flav = set(flav)
	if left > len(flav):
		print(len(flav))
	else:
		print(left)


def main():
	for _ in range(int(input())):
		(n, x) = map(int, input().split())
		l = list(map(int, input().split()))
		d = list(dict.fromkeys(l))
		if n - x > len(d):
			print(len(d))
		else:
			print(n - x)
main()


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort()
	c = len(list(set(lst)))
	if n - c >= x:
		print(c)
	else:
		print(n - x)


t = int(input())
for _ in range(t):
	(numberOfChoc, numberToSave) = map(int, input().split())
	lst = [int(y) for y in input().split()]
	numberOfDistinct = len(set(lst))
	extra = numberOfChoc - numberOfDistinct
	if extra >= numberToSave:
		print(numberOfDistinct)
	else:
		print(numberOfDistinct - (numberToSave - extra))


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	set1 = set(input().split())
	if len(set1) < n - x:
		print(len(set1))
	else:
		print(n - x)
	pass
pass


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	c = len(list(set(l)))
	if n - c >= x:
		print(c)
	else:
		print(n - x)


for tc in range(int(input())):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	A_set = list(set(A))
	N_dist = len(A_set)
	if N - X >= N_dist:
		print(N_dist)
	else:
		print(N - X)


for _ in range(int(input())):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	m = n
	fl = set()
	i = 0
	res = 0
	while n - x != 0:
		if a[i] not in fl:
			fl.add(a[i])
			res += 1
			n -= 1
		i += 1
		if i == m:
			break
	print(res)


t = int(input())
while t:
	t -= 1
	(n, x) = map(int, input().split())
	test = 0
	last_tested = 0
	li = [int(x) for x in input().split()]
	li.sort()
	for i in range(n):
		if n - test > x and li[i] > last_tested:
			test += 1
			last_tested = li[i]
	print(test)


t = int(input())
for i in range(t):
	(a, b) = list(map(int, input().split()))
	d = a - b
	flavours = set(map(int, input().split()))
	if d <= len(flavours):
		print(d)
	else:
		print(len(flavours))


t = int(input())
for _ in range(t):
	(n, x) = list(map(int, input().split()))
	chocalate = set(map(int, input().split()))
	x = n - x
	if len(chocalate) > x:
		print(x)
	else:
		print(len(chocalate))


t = int(input())
for o in range(t):
	(n, x) = map(int, input().split())
	arr = [k for k in map(int, input().split())]
	arr.sort()
	i = 0
	temp = arr[0]
	c = 1
	if n == x:
		print(0)
	else:
		while i < len(arr):
			if arr[i] != temp:
				c += 1
				temp = arr[i]
			i += 1
		rep = len(arr) - c
		if x <= rep:
			print(c)
		else:
			print(c - (x - rep))


t = int(input())
for o in range(t):
	(n, x) = map(int, input().split())
	arr = [k for k in map(int, input().split())]
	s = set()
	c = 0
	for i in arr:
		if i in s:
			c += 1
		else:
			s.add(i)
	if c >= x:
		print(len(s))
	else:
		print(len(s) - (x - c))


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	c = list(map(int, input().split()))
	if n - x == 1:
		print(1)
		continue
	remaining = n - x
	distinct = 1
	c.sort()
	for i in range(0, len(c) - 1):
		if c[i] != c[i + 1]:
			distinct += 1
	print(distinct if distinct < remaining else remaining)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	h = set(a)
	if n - len(h) >= x:
		print(len(h))
	else:
		print(n - x)


try:
	t = int(input())
	for _ in range(t):
		(n, x) = [int(i) for i in input().split()]
		arr = [int(i) for i in input().split()]
		res = {}
		for i in arr:
			if i in res:
				res[i] += 1
			else:
				res[i] = 1
		if n == x:
			print(0)
		else:
			ans = n - x
			if len(res) < ans:
				print(len(res))
			elif len(res) >= ans:
				print(ans)
except:
	EOFError


from sys import stdin, stdout

def ans():
	(n, x) = map(int, stdin.readline().strip().split())
	a = list(map(int, stdin.readline().strip().split()))
	t = len(list(set(a)))
	print(min(n - x, t))
t = int(stdin.readline())
for _ in range(t):
	ans()


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	cho = set()
	for i in range(n):
		cho.add(a[i])
	remain = int(n) - int(x)
	if remain >= len(cho):
		print(len(cho))
	else:
		print(remain)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	c = list(map(int, input().split()))
	s = 0
	cho = {}
	for i in c:
		if i in cho:
			cho[i] += 1
			s += 1
		else:
			cho[i] = 1
	if s >= x:
		print(len(cho))
	else:
		print(len(cho) - x + s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	st = [int(x) for x in input().split()]
	x = len(st)
	stt = set(st)
	m = len(stt)
	if x - m > k:
		print(m)
	else:
		print(m - (k - (x - m)))


for _ in range(int(input())):
	(n, x) = map(int, input().split(' '))
	a = list(map(int, input().split()))
	s = len(list(set(a)))
	m = min(s, n - x)
	print(m)


for _ in range(int(input())):
	(n, x) = map(int, input().split(' '))
	lst = list(map(int, input().split()))
	lst2 = list(set(lst))
	s = len(lst2)
	if n - x >= s:
		print(s)
	else:
		print(n - x)


t = int(input())
ans = []
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	gg = {}
	for i in a:
		gg[i] = gg.get(i, 0) + 1
	for val in gg:
		if gg[val] > 1:
			m = gg[val] - 1
			gg[val] = 1
			x -= m
			if x <= 0:
				break
	if x > 0:
		print(len(gg) - x)
	else:
		print(len(gg))