Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Donald Drumpf has spent the entire summer lobbying to gather votes for the upcoming student government election. At his University, there are a total of N students. Each student in the university casts a vote. The size of student government is determined by the number of students that get at least K votes.

Each person that receives at least K votes is given a post in the student government. The Dean noticed that every year, there are a few students who vote for themselves. He decided to add a rule to disqualify any such individuals who vote for themselves i.e they cannot be part of the student government. 

You are given an array A, where A_{i} denotes the person who the i-th person voted for. Can you compute the size of the student government?
 
------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
For each test case, first line consists of two space separated integers N, K.
Second line consists of N space separated integers denoting the array A,  where i-th integer denotes A_{i}.

------ Output ------ 

For each test case, output a single line containing an integer corresponding to the size of the student government.

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

$1 ≤ T ≤ 100$
$1 ≤ K ≤ N$
$1 ≤ A_{i} ≤ N$

------ Subtasks ------ 

Subtask #1: (30 points)
$1 ≤ N ≤ 3$
Subtask #2: (70 points)
$1 ≤ N ≤ 100$

----- Sample Input 1 ------ 
2
3 2
2 1 2
2 1
1 2
----- Sample Output 1 ------ 
1
0
----- explanation 1 ------ 

In first test case, there are 3 students. A student must receive at least 2
votes to be part of the student government. Student 1 votes for student 2, student 2 votes for student 1 and student 3 votes for student 2. Thus, Student 2 receives 2 votes and is the only one eligible for student government.

In second test case, although both students receive the required amount of votes, they are both disqualified as they had voted for themselves. Thus, size of the student
government is 0.

Difficulty: EASY
Tags: Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = tuple(map(int, input().split()))
	(d, count, j) = ({i: arr.count(i) for i in range(1, n + 1)}, 0, 1)
	for x in d.values():
		if x >= k and arr[j - 1] != j:
			count += 1
		j += 1
	print(count)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	(d, count, j) = ({i: a.count(i) for i in range(1, n + 1)}, 0, 1)
	for x in d.values():
		if x >= k and a[j - 1] != j:
			count += 1
		j += 1
	print(count)


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


for _ in range(int(input())):
	(n, k) = [int(y) for y in input().split()]
	lst = [int(y) for y in input().split()]
	d = {i: lst.count(i) for i in range(1, n + 1)}
	count = 0
	j = 1
	for x in d.values():
		if x >= k and lst[j - 1] != j:
			count += 1
		j += 1
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = []
	for i in range(n):
		if i + 1 == a[i]:
			a[:] = [x if x != a[i] else 0 for x in a]
	a1 = set(a)
	if a1 == {0}:
		print(0)
	else:
		c = 0
		for i in a1:
			if i != 0:
				if a.count(i) >= k:
					c += 1
		print(c)


for _ in range(int(input())):
	(total, req) = map(int, input().split())
	votes = list(map(int, input().split()))
	disq = []
	for (index, ele) in enumerate(votes, start=1):
		if ele == index:
			disq.append(ele)
	ans = 0
	for i in set(votes):
		if i not in disq and votes.count(i) >= req:
			ans += 1
	print(ans)


for _ in range(0, int(input())):
	a = [int(x) for x in input().split(' ')]
	b = [int(x) for x in input().split(' ')]
	c = set(b)
	count = 0
	for i in c:
		if b.count(i) >= a[1] and b[i - 1] != i:
			count = count + 1
	print(count)


for i in range(int(input())):
	(stu, minV) = map(int, input().split())
	students = [int(i) for i in input().split()]
	newDict = {}
	k = 0
	dequst = []
	for num in range(stu):
		if students[num] == num + 1:
			newDict[students[num]] = 0
			dequst.append(num + 1)
		elif students[num] not in dequst:
			if students[num] in newDict.keys():
				newDict[students[num]] += 1
			else:
				newDict[students[num]] = 1
	for j in newDict.values():
		if j >= minV:
			k += 1
	print(k)


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = tuple(map(int, input().split()))
	(counts, count) = (Counter(arr), 0)
	for i in range(n):
		if arr[i] == i + 1:
			counts[arr[i]] = 0
	for x in counts:
		if counts[x] >= k:
			count += 1
	print(count)


from collections import Counter
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = Counter(a)
	count = 0
	for key in c:
		if c[key] >= k and a[key - 1] != key:
			count += 1
	print(count)


for _ in range(int(input())):
	(num, m) = map(int, input().split())
	arr = tuple(map(int, input().split()))
	(d, count, j) = ({i: arr.count(i) for i in range(1, num + 1)}, 0, 1)
	for x in d.values():
		if x >= m and arr[j - 1] != j:
			count += 1
		j += 1
	print(count)


for _ in range(int(input())):
	(n, a) = map(int, input().split())
	arr = tuple(map(int, input().split()))
	(d, count, b) = ({i: arr.count(i) for i in range(1, n + 1)}, 0, 1)
	for x in d.values():
		if x >= a and arr[b - 1] != b:
			count += 1
		b += 1
	print(count)


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


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	arr = list(map(int, input().split()))
	d1 = {i: arr.count(i) for i in range(1, N + 1)}
	cnt = 0
	j = 1
	for i in d1.values():
		if i >= K and arr[j - 1] != j:
			cnt += 1
		j += 1
	print(cnt)


t = int(input())
for l in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = {}
	l1 = []
	for i in range(n):
		if a[i] != i + 1:
			if a[i] in d:
				d[a[i]] += 1
			else:
				d[a[i]] = 1
		else:
			l1.append(i + 1)
	c = 0
	for i in d:
		if d[i] >= k and i not in l1:
			c += 1
	print(c)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	m = [a[i] for i in range(len(a)) if a[i] == i + 1]
	v = []
	w = []
	for i in set(a):
		if i not in m:
			v.append(a.count(i))
			w.append(i)
	b = dict(zip(w, v))
	c = 0
	for i in range(len(b)):
		if b[w[i]] >= k:
			c += 1
	print(c)


for _ in range(int(input())):
	(buddy, januu) = map(int, input().split())
	arr = tuple(map(int, input().split()))
	(vijay, count, krish) = ({i: arr.count(i) for i in range(1, buddy + 1)}, 0, 1)
	for x in vijay.values():
		if x >= januu and arr[krish - 1] != krish:
			count += 1
		krish += 1
	print(count)


for i in range(int(input())):
	(N, K) = map(int, input().split())
	l1 = [0] * (N + 1)
	count = 0
	l = list(map(int, input().split()))
	for i in range(len(l)):
		if l[i] == i + 1:
			l1[l[i]] = -1
		elif l1[l[i]] != -1:
			l1[l[i]] += 1
	for j in l1:
		if j >= K:
			count += 1
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	f = (n + 1) * [0]
	ans = 0
	for j in range(n):
		if j + 1 == l[j]:
			f[l[j]] = -1
		elif f[l[j]] != -1:
			f[l[j]] += 1
	for j in f:
		if j >= k:
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	a = list(map(int, input().split()))
	(n, k) = (a[0], a[1])
	v = list(map(int, input().split()))
	y = []
	for i in range(len(v)):
		if v[i] == i + 1:
			if v[i] not in y:
				y.append(v[i])
	for i in y:
		c = v.count(i)
		for j in range(c):
			v.remove(i)
	s = 0
	l = []
	for i in v:
		if v.count(i) >= k and i not in l:
			s += 1
			l.append(i)
	print(s)


t = int(input())
for i in range(t):
	(n, k) = input().split(' ')
	lst = list(map(int, input().split(' ')))
	disq = 0
	nums = 0
	if disq == 0:
		for j in range(int(n)):
			counts = lst.count(j + 1)
			if counts >= int(k) and lst[j] != j + 1:
				nums = nums + 1
	print(nums)


t = int(input())

def drump(n, k, arr):
	di = {}
	disq = []
	for i in range(0, n):
		if arr[i] == i + 1:
			disq.append(arr[i])
		elif arr[i] not in di:
			di[arr[i]] = 1
		else:
			di[arr[i]] += 1
	count = 0
	for el in di:
		if di[el] >= k and el not in disq:
			count += 1
	return count
for i in range(0, t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(drump(n, k, arr))


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	j = 1
	max1 = 0
	temp = dict()
	for i in range(1, N + 1):
		temp[i] = A.count(i)
	for i in temp.values():
		if i >= K and j != A[j - 1]:
			max1 += 1
		j += 1
	print(max1)


for i in range(int(input())):
	(no_of_students, min_vote) = [int(s) for s in str(input()).split()]
	votes = [[i + 1, int(vote), 0] for (i, vote) in enumerate(str(input()).split())]
	for l in votes:
		if votes[l[1] - 1][0] != votes[l[1] - 1][1]:
			votes[l[1] - 1][2] += 1
	res = sum(map(lambda l: l[2] >= min_vote, votes))
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	votes = list(map(int, input().split()))
	voteCount = {}
	for i in range(len(votes)):
		voteIdx = votes[i] - 1
		if voteIdx in voteCount:
			if voteCount[voteIdx] is None:
				continue
			if voteIdx == i:
				voteCount[voteIdx] = None
			else:
				voteCount[voteIdx] += 1
		elif voteIdx == i:
			voteCount[voteIdx] = None
		else:
			voteCount[voteIdx] = 1
	count = 0
	for val in voteCount.values():
		if val != None and val >= k:
			count += 1
	print(count)


from collections import Counter
t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	d = {}
	for i in range(0, len(l)):
		if i + 1 != l[i]:
			d[i + 1] = l[i]
	a = d.keys()
	b = Counter(d.values())
	count = 0
	for i in b.keys():
		if i in a and b[i] >= k:
			count += 1
	print(count)
	t -= 1


t = int(input())
for times in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	dic = {}
	c = 0
	for i in range(len(arr)):
		if not dic.get(arr[i], 1):
			continue
		if i + 1 == arr[i]:
			dic[arr[i]] = None
		else:
			dic.setdefault(arr[i], 0)
			dic[arr[i]] += 1
			if dic[arr[i]] == k:
				if arr[i] != arr[arr[i] - 1]:
					c += 1
				dic[arr[i]] = None
	print(c)


n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	arry = tuple(map(int, input().split()))
	(p, count, q) = ({i: arry.count(i) for i in range(1, n + 1)}, 0, 1)
	for j in p.values():
		if j >= y and arry[q - 1] != q:
			count += 1
		q += 1
	print(count)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	lt = list(map(int, input().split()))
	lt2 = []
	lt3 = []
	s = set(lt)
	for j in s:
		if lt[j - 1] == j:
			lt2.append(j)
	for i in range(len(lt2)):
		s.remove(lt2[i])
	for x in s:
		lt3.append(lt.count(x))
	c = 0
	for i in range(len(lt3)):
		if lt3[i] >= k:
			c = c + 1
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	c = 0
	for i in range(n):
		if l[i] == i + 1:
			l1.append(l[i])
	l2 = set(l)
	for i in list(l2):
		if i in l1:
			continue
		elif l.count(i) >= k:
			c += 1
	print(c)


from collections import Counter
for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	k = Counter(l)
	for i in range(a):
		if i + 1 != l[i] and k[i + 1] >= b:
			s += 1
	print(s)


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


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	z = []
	p = []
	h = []
	for q in range(a):
		p.append(0)
	for i in range(a):
		if l[i] == i + 1:
			z.append(i + 1)
			if l[i] in h:
				h.remove(l[i])
		elif l[i] not in z:
			p[l[i] - 1] = p[l[i] - 1] + 1
			if p[l[i] - 1] == b:
				h.append(l[i])
	print(len(h))


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


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	x = 0
	l1 = []
	l2 = []
	for j in range(len(l)):
		if j + 1 == l[j]:
			l1.append(l[j])
	for i in l:
		if l.count(i) >= b and i not in l1 and (i not in l2):
			x += 1
			l2.append(i)
	print(x)


for i in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	l = []
	l1 = []
	c = 0
	for j in range(len(A)):
		if j + 1 == A[j]:
			l.append(A[j])
	for j in A:
		if A.count(j) >= K and j not in l1 and (j not in l):
			c += 1
			l1.append(j)
	print(c)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	L = list(map(int, input().split()))
	L1 = []
	c = 0
	for i in range(len(L)):
		if L[i] == i + 1:
			L1.append(L[i])
			L[i] = 0
	for i in range(1, len(L) + 1):
		if L.count(i) >= M and i not in L1:
			c += 1
	print(c)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	L = list(map(int, input().split()))
	c = 0
	for i in range(0, N):
		if L[i] != i + 1 and L.count(i + 1) >= K:
			c += 1
	print(c)


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


tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	dic = {}
	ind = 1
	lis = []
	for i in arr:
		if ind == i:
			lis.append(ind)
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
		ind += 1
	for i in lis:
		if i in dic:
			dic.pop(i)
	count = 0
	for m in dic.values():
		if m >= k:
			count += 1
	print(count)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	V = list(map(int, input().split()))
	count = 0
	for i in range(0, N):
		if V[i] != i + 1 and V.count(i + 1) >= K:
			count += 1
	print(count)