Devu has n weird friends. Its his birthday today, so they thought that this is the best occasion for testing their friendship with him. They put up conditions before Devu that they will break the friendship unless he gives them a grand party on their chosen day. Formally, ith friend will break his friendship if he does not receive a grand party on dith day.

Devu despite being as rich as Gatsby, is quite frugal and can give at most one grand party daily. Also, he wants to invite only one person in a party. So he just wonders what is the maximum number of friendships he can save. Please help Devu in this tough task !!

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- First line will contain a single integer denoting n.

- Second line will contain n space separated integers where ith integer corresponds to the day dith as given in the problem.

-----Output-----
Print a single line corresponding to the answer of the problem.

-----Constraints-----
- 1 ≤ T ≤ 104
- 1 ≤ n  ≤ 50
- 1 ≤ di ≤ 100

-----Example-----
Input:
2
2
3 2
2
1 1
Output:
2
1

-----Explanation-----
Example case 1. Devu can give party to second friend on day 2 and first friend on day 3, so he can save both his friendships.
Example case 2. Both the friends want a party on day 1, and as the Devu can not afford more than one party a day, so he can save only one of the friendships, so answer is 1.

Difficulty: EASY
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	for i in range(n):
		if a[i] in b:
			pass
		else:
			b.append(a[i])
	print(len(b))


n = int(input())
for e in range(n):
	m = int(input())
	li = list(map(int, input().split()))
	g = set(li)
	print(len(g))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	d = list(map(int, input().split()))
	c = list(Counter(d).values())
	k = 0
	for i in range(len(c)):
		if c[i] != 1:
			k += c[i] - 1
	print(n - k)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(len(set(l)))


T = int(input())
for i in range(0, T):
	N = int(input())
	a = list(map(int, input().strip().split()))[:N]
	lst = []
	count = 0
	for i in a:
		if i in lst:
			pass
		else:
			count = count + 1
			lst.append(i)
	print(count)


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


for i in range(int(input())):
	a = int(input())
	lst = list(map(int, input().split()))
	my_set = set(lst)
	count = 0
	for x in my_set:
		count += 1
	print(count)


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


for t in range(int(input())):
	n = int(input())
	numberlist = list(map(int, input().split()))
	print(len(list(set(numberlist))))


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


t = int(input())
while t:
	n = int(input())
	lt = input().split()
	for i in range(n):
		lt[i] = int(lt[i])
	new = set(lt)
	size = len(new)
	print(size)
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(c) for c in input().split()]
	l = []
	for i in a:
		if i not in l:
			l.append(i)
	print(len(l))


n = int(input())
for i in range(n):
	a = int(input())
	l = list(map(int, input().split()))
	d = []
	for j in range(len(l)):
		if l[j] not in d:
			d.append(l[j])
	print(len(d))


n = int(input())
for i in range(n):
	n1 = int(input())
	list1 = list(map(int, input().split()))
	list2 = []
	for i in list1:
		if i not in list2:
			list2.append(i)
	print(len(list2))


t = int(input())
for _ in range(t):
	n = int(input())
	s = set(map(int, input().split()))
	if n == len(s):
		print(n)
	else:
		print(len(s))


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


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


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	friends = []
	for j in arr:
		if j not in friends:
			friends.append(j)
	print(len(friends))


for _ in range(int(input())):
	n = int(input())
	d = list(map(int, input().split()))
	d = [*set(d)]
	print(len(d))


for i in range(int(input())):
	n = int(input())
	A = [int(x) for x in input().split()]
	B = set(A)
	print(len(B))


for _ in range(int(input())):
	input()
	print(len(set(input().split())))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	hsh = [0] * 101
	ans = 0
	for i in arr:
		if hsh[i] == 0:
			ans += 1
			hsh[i] += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	print(len(s))


for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	se = set(ls)
	print(len(se))


t = int(input())
for i in range(t):
	n = int(input())
	d = map(int, input().split())
	f = len(set(d))
	print(f)


t = int(input())
for i in range(t):
	c = 0
	n = int(input())
	d = list(map(int, input().split()))
	c1 = []
	for j in d:
		if j in c1:
			continue
		else:
			c1.append(j)
	print(len(c1))


t = int(input())
for i in range(t):
	n = int(input())
	ls = list(map(int, input().split()))
	s = n
	c = 1
	for j in range(n):
		count = 1
		c = 1
		if j != 0:
			for k in range(j):
				if ls[k] == ls[j]:
					c = 0
		for l in range(n):
			if ls[l] == ls[j] and l != j and (c == 1):
				count += 1
		if count > 1:
			s = s - count + 1
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	d = list(map(int, input().split()))
	l = []
	for i in d:
		if i not in l:
			l += [i]
	print(len(l))


t = int(input())
while t > 0:
	t = t - 1
	t1 = int(input())
	a = [int(c) for c in input().split()]
	l = []
	for i in a:
		if i not in l:
			l.append(i)
	print(len(l))


for i in range(int(input())):
	a = int(input())
	z = []
	l = []
	z = map(int, input().split())
	for i in z:
		if i not in l:
			l.append(i)
	print(len(l))


n = int(input())
for i in range(n):
	x = int(input())
	a = list(map(int, input().split()))
	fc = [0] * (max(a) + 1)
	for i in range(len(a)):
		if fc[a[i]] == 0:
			fc[a[i]] += 1
	print(sum(fc))


t = int(input())
for i in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	a = set(li)
	l = list(a)
	print(len(l))


t = int(input())
for i in range(t):
	a = int(input())
	l = list(map(int, input().split(' ')))
	s = set(l)
	print(len(s))


t = int(input())
for x in range(t):
	n = int(input())
	a = [int(c) for c in input().split()]
	ll = []
	for i in a:
		if i not in ll:
			ll.append(i)
	print(len(ll))


for _ in range(int(input())):
	n = int(input())
	s = input().split(' ')
	a = set()
	for i in range(n):
		a.add(eval(s[i]))
	print(len(a))


for i in range(int(input())):
	n = int(input())
	L = input().split()
	l = [eval(i) for i in L]
	a = []
	for i in range(len(l)):
		if l[i] not in a:
			a.append(l[i])
	print(len(a))


a = int(input())
while a:
	a = a - 1
	b = int(input())
	x = list(map(int, input().split()))
	p = []
	for i in x:
		if i not in p:
			p.append(i)
	print(len(p))


t = int(input())
while t > 0:
	n = int(input())
	li = list(map(int, input().split(' ')))
	se = list(set(li))
	print(len(se))
	t -= 1


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	l1 = list(set(l))
	print(len(l1))
	t = t - 1


t = int(input())
i = 0
while i < t:
	n = int(input())
	a = []
	a = input().split()
	j = 0
	b = []
	fl = 0
	while j < n:
		x = int(a[j])
		if x not in b:
			c = a.count(a[j])
			if c > 1:
				fl = fl + c - 1
			b.append(x)
		j += 1
	fs = n - fl
	print(fs)
	i += 1


a = int(input())
for i in range(a):
	b = int(input())
	c = set()
	d = map(int, input().split())
	for j in d:
		c.add(j)
	print(len(c))


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


for i in range(int(input())):
	n = int(input())
	s = set(map(int, input().split()))
	print(len(s))


n = int(input())
for i in range(n):
	b = int(input())
	lst = list(map(int, input().split()))
	s1 = set(lst)
	print(len(s1))


t = int(input())
for i in range(t):
	n = int(input())
	x = set()
	d = list(map(int, input().split()))
	for j in d:
		x.add(j)
	print(len(x))


t = int(input())
for i in range(t):
	n = int(input())
	s = []
	l = list(map(int, input().split()))
	for i in l:
		if i not in s:
			s.append(i)
		else:
			continue
	print(len(s))


t = int(input())
for i in range(t):
	c = 0
	n = int(input())
	d = list(map(int, input().split()))
	c1 = []
	res = [*set(d)]
	print(len(res))


T = int(input())
for i in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(set(a))
	c = len(b)
	print(c)


test = int(input())
for _ in range(0, test):
	n = int(input())
	lister = set(map(int, input().split()))
	print(len(lister))


for i in range(int(input())):
	n = int(input())
	a = [int(c) for c in input().split()]
	l1 = []
	for i in a:
		if i not in l1:
			l1.append(i)
	print(len(l1))


T = int(input())
for i in range(0, T):
	n = int(input())
	list = [int(c) for c in input().split()]
	count = 0
	unique = []
	for i in list:
		if i not in unique:
			unique.append(i)
			count = count + 1
	print(count)


for i in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	x = set(m)
	print(len(x))


t = int(input())
while t != 0:
	dict = {}
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(n):
		if arr[i] in dict:
			dict[arr[i]] += 1
		else:
			dict[arr[i]] = 1
	print(len(dict))
	t -= 1


for i in range(int(input())):
	n = int(input())
	d = list(map(int, input().split()))
	s = set(d)
	s_len = len(s)
	if n == s_len:
		print(n)
	else:
		print(s_len)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for i in l:
		if i not in l1:
			l1.append(i)
	print(len(l1))


for i in range(int(input())):
	f = int(input())
	arr = list(map(int, input().split()))
	newarr = set(arr)
	l = len(newarr)
	if l == f:
		print(f)
	else:
		print(l)


for i in range(int(input())):
	n = int(input())
	test = list(map(int, input().split()))
	set1 = set(test)
	print(len(set1))


t = int(input())
l = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a1 = set(a)
	print(len(a1))


t = int(input())
for i in range(t):
	n = int(input())
	li = list(map(int, input().split()))[:n]
	a = []
	for i in li:
		if li.count(i) == 1:
			a.append(i)
		if i not in a:
			a.append(i)
	print(len(a))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	set_a = set()
	set_a.update(a)
	print(len(set_a))


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


t = int(input())
while t > 0:
	n = int(input())
	s = list(map(int, input().split()))
	li = []
	count = 0
	for i in range(n):
		if s[i] not in li:
			li.append(s[i])
			count += 1
		else:
			continue
	print(count)
	t -= 1


T = int(input())
for i in range(T):
	N = int(input())
	D = list(map(int, input().split()))
	unique_D = list(set(D))
	print(len(unique_D))


t = int(input())
for _ in range(t):
	n = int(input())
	ls = list(map(int, input().split()))
	s = len(set(ls))
	print(s)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	n1 = list(map(int, input().split()))
	z = Counter(n1).items()
	ans = 0
	c = 0
	for i in z:
		if i[1] == 1:
			ans += 1
		else:
			c += 1
	print(ans + c)