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

Alice has quarreled with Berta recently. Now she doesn't want to have anything in common with her!
Recently, they've received two collections of positive integers. The Alice's integers were A_{1}, A_{2}, ..., A_{N}, while Berta's were B_{1}, B_{2}, ..., B_{M}.
Now Alice wants to throw away the minimal amount of number from her collection so that their collections would have no common numbers, i.e. there won't be any number which is present in both collections. Please help Alice to find the minimal amount of numbers she would need to throw away.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integer numbers N and M denoting the amount of numbers in Alice's and Berta's collections respectively.

The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the numbers of Alice. 

The third line contains M space-separated integers B_{1}, B_{2}, ..., B_{M} denoting the numbers of Berta. 

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

For each test case, output a single line containing the minimal amount of numbers Alice needs to throw away from her collection so that she wouldn't have any numbers in common with Berta.

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

$1 ≤ A_{i}, B_{i}  ≤ 10^{6}$
$All numbers are distinct within a single girl's collection.$

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

$Subtask #1 (47 points): T = 25, 1 ≤ N, M ≤ 1000$
$Subtask #2 (53 points): T = 5, 1 ≤ N, M ≤ 100000$

----- Sample Input 1 ------ 
2
3 4
1 2 3
3 4 5 6
3 3
1 2 3
4 5 6
----- Sample Output 1 ------ 
1
0
----- explanation 1 ------ 
Example case 1. If Alice throws away the number 3 from her collection, she would obtain {1, 2} which is disjoint with {3, 4, 5, 6}.
Example case 2. Girls don't have any number in common initially. So there is no need to throw away any number.

Source: codechef | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions:
for h in range(int(input())):
	(p, q) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	s = list(map(int, input().split()))
	l = set(l)
	s = set(s)
	c = 0
	for h in l:
		if h in s:
			c += 1
	print(c)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	a = set(a)
	b = set(b)
	b = a.intersection(b)
	print(len(b))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	la = set([int(x) for x in input().split()])
	lb = set([int(x) for x in input().split()])
	c = la.difference(lb)
	print(a - len(c))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(c, d) = (set((int(x) for x in input().split())), set((int(x) for x in input().split())))
	c = c.difference(d)
	print(a - len(c))


a = int(input())
for i in range(a):
	b = list(map(int, input().rstrip().split()))
	c = list(map(int, input().rstrip().split()))
	d = list(map(int, input().rstrip().split()))
	c = set(c)
	d = set(d)
	count = 0
	m = c & d
	print(len(m))


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l3 = []
	l3.extend(l1)
	l3.extend(l2)
	n = len(l3)
	s = set(l3)
	r = list(s)
	n2 = len(r)
	print(n - n2)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	a1 = set(map(int, input().split()))
	b1 = set(map(int, input().split()))
	print(len(a1) - len(a1 - b1))


for i in range(int(input())):
	(N, M) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	s1 = set(l1)
	s2 = set(l2)
	de = 0
	for i in s1:
		if i in s2:
			de += 1
	print(de)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	lst = set(map(int, input().split()))
	lst1 = set(map(int, input().split()))
	print(n - len(lst.difference(lst1)))


test = int(input())
for i in range(test):
	k = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = set(a)
	d = set(b)
	e = c.intersection(d)
	print(len(e))


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


for _ in range(0, int(input())):
	(n, m) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	alc = set(a)
	brt = set(b)
	cnt = 0
	for x in alc:
		if x in brt:
			cnt += 1
	print(cnt)


t = int(input())
for i in range(t):
	(N, M) = map(int, input().split())
	A = sorted(list(map(int, input().split())))
	B = sorted(list(map(int, input().split())))
	C = list(set(A + B))
	print(N + M - len(C))


t = int(input())
for i in range(t):
	(N, M) = map(int, input().split())
	A = sorted(list(map(int, input().split())))
	B = sorted(list(map(int, input().split())))
	count = 0
	A_unique = list(set(A))
	B_unique = list(set(B))
	union = A_unique + B_unique
	union_unique = list(set(union))
	length = N - len(A_unique) + (len(A_unique) + len(B_unique) - len(union_unique))
	print(length)


t = int(input())
for i in range(0, t):
	(x, y) = map(int, input().split(' '))
	a = input().split(' ')
	b = input().split(' ')
	a = a + b
	a = list(dict.fromkeys(a))
	print(x + y - len(a))


test_cases = int(input())
for i in range(test_cases):
	str_num = input()
	a = input().split()
	b = input().split()
	for i in range(len(a)):
		a[i] = int(a[i])
	for i in range(len(b)):
		b[i] = int(b[i])
	a.sort()
	b.sort()
	done = False
	p1 = 0
	p2 = 0
	count = 0
	while not done:
		if p1 >= len(a) or p2 >= len(b):
			done = True
		elif a[p1] < b[p2]:
			p1 += 1
		elif a[p1] > b[p2]:
			p2 += 1
		elif a[p1] == b[p2]:
			count += 1
			p1 += 1
			p2 += 1
	print(count)


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	s = list(map(int, input().split()))
	l = set(l)
	s = set(s)
	c = 0
	for i in l:
		if i in s:
			c += 1
	print(c)


for t in range(int(input())):
	l = 0
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(len(set(a) & set(b)))


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


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


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split(' '))
	lisa = list(map(int, input().split(' ')))
	lisb = list(map(int, input().split(' ')))
	lisa.sort()
	lisb.sort()
	remove = 0
	while a and b:
		r = lisa.pop()
		while b > 0 and r < lisb[-1]:
			lisb.pop()
			b = b - 1
		if b and r == lisb[-1]:
			lisb.pop()
			b = b - 1
			remove += 1
		a -= 1
	print(remove)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().strip().split())
	arr = {int(i) for i in input().strip().split()}.union({int(i) for i in input().strip().split()})
	print(n + m - len(arr))


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	B = set(list(map(int, input().split())))
	knt = 0
	for i in range(N):
		if A[i] in B:
			knt += 1
	print(knt)


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


for _ in range(int(input())):
	[n1, n2] = list(map(int, input().split()))
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	print(len(set(x) & set(y)))


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


n = int(input())
for i in range(n):
	(m, n) = [int(i) for i in input().split(' ')]
	lst = [int(i) for i in input().split(' ')][:m]
	lst1 = [int(i) for i in input().split(' ')][:n]
	list1 = set(lst + lst1)
	print(m + n - len(list1))


t = input()
for c in range(0, int(t)):
	(n, m) = input().split()
	a = input().split()
	b = input().split()
	a = set(a)
	b = set(b)
	ab = a & b
	print(len(ab))


t = int(input())
for i in range(t):
	strNum = input()
	str1 = input()
	str2 = input()
	setA = set(str1.split())
	setB = set(str2.split())
	newSetA = setA & setB
	print(len(newSetA))


for x in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a = set(a)
	b = set(b)
	v = 0
	for x in a:
		if x in b:
			v += 1
	print(v)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	l_n = list(map(int, input().split()))
	l_m = list(map(int, input().split()))
	set_n = set(l_n)
	set_m = set(l_m)
	for i in set_n:
		if i in set_m:
			ans += 1
	print(ans)


t = int(input())
for _ in range(0, t):
	(n, m) = map(int, input().split())
	s1 = list(map(int, input().split()))
	s2 = list(map(int, input().split()))
	s = sorted(s1 + s2)
	d = s[0]
	j = 0
	for i in s[1:len(s)]:
		if d == i:
			j += 1
		d = i
	print(j)


def main():
	testcases = int(input())
	i = 0
	while i < testcases:
		(N, M) = input().split()
		N = int(N)
		M = int(M)
		list_alice = input().split()
		list_berta = input().split()
		for j in range(N):
			list_alice[j] = int(list_alice[j])
		for j in range(M):
			list_berta[j] = int(list_berta[j])
		list_alice.sort()
		list_berta.sort()
		index_alice = 0
		index_berta = 0
		count = 0
		while index_alice <= len(list_alice) - 1 and index_berta <= len(list_berta) - 1:
			if list_alice[index_alice] > list_berta[index_berta]:
				index_berta += 1
			elif list_alice[index_alice] < list_berta[index_berta]:
				index_alice += 1
			else:
				count += 1
				index_alice += 1
				index_berta += 1
		print(count)
		i += 1
main()


def solve():
	(n, m) = map(int, input().split())
	Alst = set(map(int, input().split()))
	Blst = set(map(int, input().split()))
	if n > m:
		f = Alst.intersection(Blst)
		print(len(f))
	else:
		f = Blst.intersection(Alst)
		print(len(f))

def max(a, b):
	if a > b:
		return a
	else:
		return b
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	nm = input()
	a = input()
	a = a.split()
	d = {'-1': 0}
	for i in range(len(a)):
		d[a[i]] = 1
	b = input()
	b = b.split()
	k = 0
	for i in range(len(b)):
		if b[i] in d:
			k = k + 1
	print(k)


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


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = set(map(int, input().split()))
	b = set(map(int, input().split()))
	count = 0
	c = a.intersection(b)
	print(len(c))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	count = 0
	d = {}
	for i in b:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in a:
		if i in d:
			count += 1
	print(count)


for _ in range(int(input())):
	__ = input()
	A = set(map(int, input().split()))
	B = set(map(int, input().split()))
	print(len(A.intersection(B)))


t = int(input())
for i in range(t):
	m = list(map(int, input().split()))
	arr1 = set(list(map(int, input().split())))
	arr2 = set(list(map(int, input().split())))
	count = 0
	for j in arr1:
		if j in arr2:
			count += 1
	print(count)


t = int(input())
for i in range(t):
	x = input()
	n = list(map(int, input().split()))
	m = set(list(map(int, input().split())))
	cnt = 0
	for i in n:
		if i in m:
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	ln = input()
	n = list(map(int, input().split()))
	m = set(list(map(int, input().split())))
	cnt = 0
	for i in n:
		if i in m:
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(j) for j in input().split()]
	b = [int(x) for x in input().split()]
	c = a + b
	cnt = 0
	mp = {}
	for i in range(len(c)):
		if c[i] in mp:
			cnt += 1
		else:
			mp[c[i]] = i
	print(cnt)


tests = int(input())
for i in range(tests):
	(alice, bertha) = map(int, input().split())
	alice_set = set(map(int, input().split()))
	bertha_set = set(map(int, input().split()))
	print(len(alice_set.intersection(bertha_set)))


for i in range(int(input())):
	l = []
	(n, m) = map(int, input().split())
	N = set(map(int, input().split()))
	M = set(map(int, input().split()))
	s = N.intersection(M)
	print(len(s))


def main():
	from sys import stdin, stdout
	t = int(stdin.readline())

	def f(a, b):
		return len(a.intersection(b))
	for i in range(t):
		(n, m) = map(int, stdin.readline().split())
		(*a,) = stdin.readline().split()
		(*b,) = stdin.readline().split()
		stdout.write(str(f(set(a), set(b))) + '\n')
main()


from math import gcd, sqrt, ceil, floor, log10
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
sys.setrecursionlimit(3000000)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(1000000000.0) + 7
NEWLINE = '\n'
SPACE = ' '
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))

def solve(*args, **kwargs):
	(n, m, arr1, arr2) = args
	res = 0
	for (k, v) in arr1.items():
		if k in arr2 and v > 0:
			res += 1
			arr1[k] -= 1
			arr2[k] -= 1
	for (k, v) in arr2.items():
		if k in arr1 and v > 0:
			res += 1
			arr1[k] -= 1
			arr2[k] -= 1
	return res

def main(*args, **kwargs):
	for _ in range(int(input())):
		(arg1, arg2) = inp_vars(int, SPACE)
		arg3 = inp_vars(int, SPACE, Counter)
		arg4 = inp_vars(int, SPACE, Counter)
		res = solve(*(arg1, arg2, arg3, arg4))
		if type(res) in {list, tuple, set}:
			print(*res, sep=' ')
		else:
			print(res)
main()


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	arr = set(arr1 + arr2)
	print(a + b - len(arr))


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


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	a1 = list(sorted(map(int, input().split())))
	b1 = list(sorted(map(int, input().split())))
	(i, j, s) = (0, 0, 0)
	while i < a and j < b:
		if a1[i] == b1[j]:
			s += 1
			i += 1
			j += 1
		elif a1[i] > b1[j]:
			j += 1
		else:
			i += 1
	print(s)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	a1 = set(map(int, input().split()))
	b1 = set(map(int, input().split()))
	s = a1.intersection(b1)
	print(len(s))


t = int(input())
while t:
	(n, m) = map(int, input().split())
	a = set(map(int, input().split()))
	b = set(map(int, input().split()))
	c = b.intersection(a)
	print(len(c))
	t -= 1


from collections import Counter
for _ in [0] * int(input()):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a = set(arr)
	b = set(b)
	c = b.intersection(a)
	print(len(c))


for _ in range(int(input())):
	(a, b) = list(map(int, input().split(' ')))
	al = list(map(int, input().split(' ')))
	be = list(map(int, input().split(' ')))
	l = set(be).intersection(set(al))
	print(len(l))


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


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


test = int(input())
for t in range(test):
	(n, m) = list(map(int, input().split(' ')))
	alice = list(map(int, input().split(' ')))
	bertha = list(map(int, input().split(' ')))
	x = set(alice).intersection(set(bertha))
	print(len(x))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(y) for y in input().split()]
	a1 = set(a)
	b1 = set(b)
	d = {}
	for i in a1:
		if i not in d:
			d[i] = 1
	for j in b1:
		if j in d:
			d[j] += 1
	count = 0
	for m in a1:
		if d[m] > 1:
			count += 1
	print(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = 0
	a1 = set(a)
	b1 = set(b)
	x = a1.intersection(b1)
	x = list(x)
	print(len(x))


t = int(input())
while t:
	[n, m] = map(int, input().split())
	a = map(int, input().split())
	b = map(int, input().split())
	s1 = set(a)
	s2 = set(b)
	print(len(s1.intersection(s2)))
	t -= 1


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	ln1 = len(a)
	a = list(set(a) - set(b))
	ln2 = len(a)
	print(ln1 - ln2)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l = l1 + l2
	s = set(l)
	print(len(l) - len(s))


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


for t in range(int(input())):
	(n, m) = map(int, input().split())
	valuesa = input().split()
	valuesb = input().split()
	a = set(valuesa)
	b = set(valuesb)
	print(len(a.intersection(b)))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	a = set(a)
	b = set(b)
	c = a & b
	print(len(c))