Professor Sahil is a master artist, he always finds creative ways to teach lessons to his students.
Today in Painting class he took all the students of the class to a wall. Professor Sahil asked every student to paint the wall upto a certain integral height one by one (second boy starts once the first boy finishes painting) from the bottom with any color of their wish, except a student Mudit who was made to stand behind the wall and note down all the data i.e the height upto which each student painted and the color $Ci$ every student used. At the end of the painting session Professor asked Mudit to tell how many distinct colors are there on the wall. Mudit being a weak student asked you for help.

Formally, given a wall of infinite height, initially unpainted. There occur $N$ operations, and in ith operation, the wall is painted upto height $Hi$ with color $Ci$. Suppose in jth operation (j>i) wall is painted upto height $Hj$ with color $Cj$ such that $Hj$ ≥ $Hi$, the $Cith$ color on the wall is hidden. At the end of $N$ operations, you have to find the number of distinct colors(≥1) visible on the wall.

Help him find out the number of distinct colors on the wall.

------ Input: ------

The first line consists of single integer $T$ denoting the number of test cases.
The second line contains 2 space separated integers $N$ and $M$, denoting the number of students and number of colors available (1 to $M$).
The third line contains $N$-space separated integers ($Hi$ ) denoting the height upto which each student painted the wall.
The fourth line contains $N$ space separated integers denoting the color ( $Ci$ ) the ith student used.

------ Output: ------
Print the number for distinct colors on the wall for each test case.

------ Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ,M ≤ 10^{5}$
Sum of N over all test cases ≤ $5*10^{5}$
Sum of M over all test cases ≤$5*10^{5}$
$1 ≤ Hi ≤10^{9}$
$1 ≤ Ci ≤ M$

------ Sample Input: ------
	
------ Sample Output: ------
	
###EXPLANATION:

----- Sample Input 1 ------ 
3
5 4
1 2 3 4 5
3 3 3 3 3
5 4
3 5 1 2 3
1 2 3 4 3
5 5 
5 4 3 2 3
1 2 3 4 5
----- Sample Output 1 ------ 
1
2
3
----- explanation 1 ------ 
In the first test case, painted upto height 1, 2, 3, 4, 5 in the five operations, all with the same color. Hence, the number of distinct colors is 1.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Implementation


Solutions:
t = int(input())
for j in range(t):
	(n, m) = map(int, input().split())
	w = list(map(int, input().split()))
	c = list(map(int, input().split()))
	ans = []
	ans.append(c[n - 1])
	bm = w[n - 1]
	for i in range(n - 2, -1, -1):
		if w[i] > bm:
			ans.append(c[i])
			bm = w[i]
	print(len(list(set(ans))))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	p = h[n - 1]
	c1 = [c[n - 1]]
	for i in range(n - 2, -1, -1):
		if h[i] > p:
			c1.append(c[i])
			p = h[i]
	c2 = set(c1)
	print(len(c2))


from sys import *

def solve():
	(n, m) = map(int, input().strip().split(' '))
	h = list(map(int, input().strip().split(' ')))
	c = list(map(int, input().strip().split(' ')))
	cw = [0] * (m + 1)
	mh = 0
	for i in range(n - 1, -1, -1):
		if h[i] > mh:
			cw[c[i]] = 1
			mh = h[i]
	print(sum(cw))
for _ in range(int(input().strip())):
	solve()


t = int(input())
for _ in range(t):
	(nos, noc) = map(int, input().split())
	h = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	s = []
	f = [0] * (noc + 1)
	for i in range(nos):
		while s and s[-1][0] <= h[i]:
			f[s[-1][1]] -= 1
			s.pop()
		s.append([h[i], c[i]])
		f[c[i]] += 1
	ans = 0
	for i in f:
		if i > 0:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	c = list(map(int, input().split()))
	mp = {}
	for i in set(c):
		mp[i] = 0
	(curr, ans) = (-1, 0)
	for i in range(1, n + 1):
		if l[-i] > curr:
			mp[c[-i]] = 1
		curr = max(curr, l[-i])
	for i in set(c):
		if mp[i] == 1:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	height = list(map(int, input().split()))
	color = list(map(int, input().split()))
	wall = [-1] * (n + 1)
	col = set()
	for i in range(n - 1, -1, -1):
		wall[i] = max(height[i], wall[i + 1])
	for i in range(n):
		h = wall[i + 1]
		if height[i] > h:
			col.add(color[i])
	print(len(col))


from math import ceil
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	ans = 0
	suff_max = [-1] * (n + 1)
	for i in range(n - 1, -1, -1):
		suff_max[i] = max(h[i], suff_max[i + 1])
	col = set()
	for i in range(n):
		max_h = suff_max[i + 1]
		if h[i] > max_h:
			col.add(c[i])
	ans = len(col)
	print(ans)


def snek(i, n, h):
	for j in range(i + 1, n):
		if h[j] >= h[i]:
			return False
	return True
t = int(input())
for i in range(t):
	(n, c) = map(int, input().split())
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	d = []
	for j in range(n - 1):
		if snek(j, n, h) and c[j] not in d:
			d.append(c[j])
	if c[n - 1] not in d:
		d.append(c[n - 1])
	print(len(d))


def check(i, n, height):
	for j in range(i + 1, n):
		if height[j] >= height[i]:
			return False
	return True
T = int(input())
for _ in range(T):
	(n, c) = map(int, input().split())
	height = list(map(int, input().split()))
	colors = list(map(int, input().split()))
	distinct_colors = []
	for i in range(n - 1):
		if check(i, n, height) and colors[i] not in distinct_colors:
			distinct_colors.append(colors[i])
	if colors[n - 1] not in distinct_colors:
		distinct_colors.append(colors[n - 1])
	print(len(distinct_colors))


t = int(input())
while t:
	(n, m) = map(int, input().split())
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	cw = [0] * (m + 1)
	h = h[::-1]
	c = c[::-1]
	mh = 0
	for i in range(n):
		if h[i] > mh:
			cw[c[i]] = 1
			mh = h[i]
	print(sum(cw))
	t -= 1


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	w = dict()
	for i in range(m):
		if a[i] in w:
			w[a[i]].append(i)
		else:
			w[a[i]] = [i]
	eles = sorted(list(w.keys()), reverse=True)
	current = 0
	color = set()
	eles_length = len(eles)
	for i in range(eles_length):
		if w[eles[i]][-1] >= current:
			current = w[eles[i]][-1]
			color.add(b[current])
	print(len(color))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	H = list(map(int, input().split()))
	C = list(map(int, input().split()))
	i = n - 1
	s = set()
	max_h = 0
	while i >= 0:
		if H[i] > max_h:
			max_h = H[i]
			s.add(C[i])
		i -= 1
	print(len(s))


def distinct_colors(n, m, a, c):
	u = [(a[i], c[i]) for i in range(n)]
	u = u[::-1]
	max_height = u[0][0]
	colors = [u[0][1]]
	for x in range(1, len(u)):
		if u[x][0] > max_height:
			max_height = u[x][0]
			if u[x][1] not in colors:
				colors.append(u[x][1])
		else:
			continue
	print(len(colors))
for _ in range(int(input())):
	(n, m) = list(map(int, input().rsplit()[:2]))
	h = list(map(int, input().rsplit()[:n]))
	c = list(map(int, input().rsplit()[:n]))
	distinct_colors(n, m, h, c)


T = int(input())
for i in range(T):
	(N, M) = [int(i) for i in input().split()]
	heights = [int(i) for i in input().split()]
	colors = [int(i) for i in input().split()]
	units = [(heights[i], colors[i]) for i in range(len(heights))]
	units = units[::-1]
	max_height = units[0][0]
	colors = [units[0][1]]
	for x in range(1, len(units)):
		if units[x][0] > max_height:
			max_height = units[x][0]
			if units[x][1] not in colors:
				colors.append(units[x][1])
		else:
			continue
	print(len(colors))


t = int(input())
for z in range(t):
	nm = list(map(int, input().split()))
	n = nm[0]
	m = nm[1]
	hl = list(map(int, input().split()))
	cl = list(map(int, input().split()))
	c = []
	while len(hl) >= 1:
		h = max(hl)
		for i in range(len(hl)):
			if hl[i] == h:
				hi = i
		del hl[0:hi + 1]
		c.append(cl[hi])
		del cl[0:hi + 1]
	print(len(set(c)))


t = int(input())
for i in range(t):
	a = input()
	(n, m) = (int(a.split()[0]), int(a.split()[1]))
	A = input()
	h = list(map(int, A.split()))
	B = input()
	c = list(map(int, B.split()))
	li = [h[0]]
	co = [c[0]]
	k = 0
	for i in range(1, n):
		if h[i] < li[k]:
			li.append(h[i])
			co.append(c[i])
			k = k + 1
		else:
			while 1:
				li.pop()
				co.pop()
				k = k - 1
				if k == -1 or h[i] < li[k]:
					li.append(h[i])
					co.append(c[i])
					k = k + 1
					break
	p = set(co)
	print(len(p))


T = int(input())
a = {}
s = {1}
s.clear()
for i in range(T):
	(N, K) = map(int, input().split())
	H = list(map(int, input().split()))
	C = list(map(int, input().split()))
	a.clear()
	s.clear()
	ind = -1
	while True:
		H = H[ind + 1:N]
		C = C[ind + 1:N]
		ind = H.index(max(H))
		if ind == len(H) - 1:
			a[H[ind]] = C[ind]
			break
		else:
			a[H[ind]] = C[ind]
	for j in a.values():
		s.add(j)
	print(len(s))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	h.reverse()
	c.reverse()
	m = 0
	z = []
	for i in range(n):
		if h[i] > m:
			z.append(c[i])
			m = h[i]
	print(len(set(z)))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	height = list(map(int, input().split()))
	color = list(map(int, input().split()))
	count = 0
	wall = height[-1]
	check = [color[-1]]
	for i in range(n - 2, -1, -1):
		if height[i] > wall:
			wall = height[i]
			check.append(color[i])
	print(len(set(check)))


def findmax_index(height, color, low, high, L, M):
	number = 0
	index = low
	for i in range(low, high):
		if height[i] >= number:
			number = height[i]
			index = i
	L.append(number)
	M.append(color[index])
	if index == high - 1:
		return (L, M)
	else:
		return findmax_index(height, color, index + 1, high, L, M)
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	height = [int(x) for x in input().split()]
	color = [int(x) for x in input().split()]
	L = []
	M = []
	(A, B) = findmax_index(height, color, 0, N, L, M)
	z = set(B)
	print(len(z))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = a[-1]
	s = [b[-1]]
	for i in range(n - 2, -1, -1):
		if a[i] > d:
			d = a[i]
			s.append(b[i])
	print(len(set(s)))


t = int(input())
for i in range(0, t):
	(n, m) = [int(x) for x in input().split()]
	str1 = [int(x) for x in input().split()]
	str2 = [int(x) for x in input().split()]
	count = 1
	maxi = max(str1)
	for i in range(len(str1) - 1, -1, -1):
		if str1[i] == maxi:
			pro = i
			break
	arr2 = []
	arr3 = []
	for i in range(pro, len(str1)):
		arr2.append(str1[i])
		arr3.append(str2[i])
	arr = []
	for i in range(0, len(arr2)):
		for j in range(i + 1, len(arr2)):
			if arr2[i] <= arr2[j]:
				break
		else:
			arr.append(arr3[i])
	print(len(list(set(arr))))


for t in range(int(input())):
	(n, m) = map(int, input().split())
	h = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	col = [0] * 1000000
	maxo = h[-1]
	col[c[-1]] = 1
	for i in range(n - 1, -1, -1):
		if maxo < h[i]:
			maxo = h[i]
			col[c[i]] = 1
	s = sum(col)
	print(s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	h = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	i = n - 1
	ch = 0
	color = []
	while i >= 0:
		if h[i] > ch:
			ch = h[i]
			color.append(c[i])
		i -= 1
	print(len(set(color)))


def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		heap = list()
		from heapq import heappush, heappop
		for (h, c) in zip(map(int, input().split()), map(int, input().split())):
			while len(heap) > 0 and heap[0][0] <= h:
				heappop(heap)
			heappush(heap, (h, c))
		print(len(set((c for (h, c) in heap))))
main()


t = int(input())
while t:
	(n, m) = input().split()
	l = list(map(int, input().split()))
	k = list(map(int, input().split()))
	l1 = []
	k1 = []
	l1 = l[::-1]
	k1 = k[::-1]
	maxx = l1[0]
	clr = k1[0]
	c = 1
	l2 = []
	l2.append(k1[0])
	for i in range(int(n)):
		if l1[i] > maxx:
			maxx = l1[i]
			if k1[i] not in l2:
				c += 1
			l2.append(k1[i])
	print(c)
	t -= 1


def testing(N, M, H, C):
	R = [(H[0], C[0])]
	for i in range(1, N):
		l = len(R)
		while l != 0 and R[l - 1][0] <= H[i]:
			(h, c) = R.pop()
			l = len(R)
		R.append([H[i], C[i]])
	print(len(set([c[1] for c in R])))

def main():
	T = int(input())
	dMatrix = {}
	for i in range(T):
		(N, M) = [int(item) for item in input().split()]
		H = [int(item) for item in input().split()]
		C = [int(item) for item in input().split()]
		dMatrix[i] = (N, M, H, C)
	for (k, v) in dMatrix.items():
		(N, M, H, C) = v
		testing(N, M, H, C)
main()


for _ in range(int(input())):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	c.append(0)
	color = []
	height = 0
	index = n
	for i in range(n - 1, -1, -1):
		if height < h[i]:
			height = h[i]
			if c[index] != c[i]:
				color.append(c[i])
	color = set(color)
	print(len(color))


for i in range(int(input())):
	(n, m) = map(int, input().strip().split(' '))
	l1 = list(map(int, input().strip().split(' ')))
	l2 = list(map(int, input().strip().split(' ')))
	cnt = [l2[-1]]
	m = l1[-1]
	for j in range(n - 2, -1, -1):
		if m < l1[j]:
			cnt.append(l2[j])
			m = l1[j]
	print(len(set(cnt)))


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a1 = [[a[i], i] for i in range(n)]
	b = [int(x) for x in input().split()]
	w = set()
	a1.sort(reverse=True)
	w.add(b[a1[0][1]])
	u = a1[0][1]
	for x in range(1, n):
		if a1[x][1] > u:
			w.add(b[a1[x][1]])
			u = a1[x][1]
	o = 0
	for x in w:
		o += 1
	print(o)


import bisect
t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().strip().split())
	h = list(map(int, input().strip().split()))
	c = list(map(int, input().strip().split()))
	ct = 0
	s = set([c[-1]])
	mx = h[-1]
	for i in range(n - 2, -1, -1):
		if h[i] > mx:
			s.add(c[i])
			mx = h[i]
	print(len(s))


def main():
	for i in range(0, int(input())):
		(n, m) = list(map(int, input().split()))
		h = list(map(int, input().split()))
		c = list(map(int, input().split()))
		j = h.index(max(h))
		h = h[j:]
		c = c[j:]
		index = []
		new_c = []
		for j in range(0, len(h)):
			for k in range(j + 1, len(h)):
				if h[j] <= h[k]:
					break
			else:
				new_c.append(c[j])
		print(len(list(set(new_c))))
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	H = list(map(int, input().split()))
	C = list(map(int, input().split()))
	ch = [H[0]]
	cc = [C[0]]
	for i in range(1, len(H)):
		if max(ch) <= H[i]:
			ch = [H[i]]
			cc = [C[i]]
		else:
			while H[i] >= ch[-1]:
				ch.pop()
				cc.pop()
			ch.append(H[i])
			cc.append(C[i])
	print(len(set(cc)))


t = int(input())
for _ in range(t):
	(n, y) = map(int, input().split())
	a = [int(y) for y in input().split()]
	b = [int(y) for y in input().split()]
	m = a[-1]
	ans = []
	ans.append(b[-1])
	for i in range(n - 2, -1, -1):
		if a[i] > m:
			m = a[i]
			ans.append(b[i])
	print(len(set(ans)))


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	H = list(map(int, input().split()))
	C = list(map(int, input().split()))
	d = {}
	for i in range(N):
		d[H[i]] = C[i]
	H.reverse()
	count = 1
	max1 = H[0]
	s = set()
	s.add(d[H[0]])
	for i in range(N - 1):
		if max1 < H[i + 1]:
			s.add(d[H[i + 1]])
			max1 = H[i + 1]
	print(len(s))


from bisect import bisect_right
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	hh = map(int, input().split())
	cc = map(int, input().split())
	rr = []
	ww = []
	for (h, c) in zip(hh, cc):
		i = bisect_right(rr, h)
		rr = rr[i:]
		ww = ww[i:]
		rr.insert(0, h)
		ww.insert(0, c)
	print(len(set(ww)))


t = int(input())
for i in range(t):
	a = input()
	n = int(a.split()[0])
	m = int(a.split()[1])
	c = input()
	d = input()
	e = list(map(int, c.split()))
	f = list(map(int, d.split()))
	l = []
	for j in range(n):
		flag = 0
		for k in range(j + 1, n):
			if e[j] <= e[k]:
				flag = 1
				break
		if flag == 0:
			l.append(f[j])
	s = set(l)
	print(len(s))


t = int(input())
for i in range(t):
	q = input().split()
	n = int(q[0])
	m = int(q[1])
	h = [int(j) for j in input().split()]
	c = [int(j) for j in input().split()]
	s = h[0:]
	ind = 0
	col = []
	count = 1
	while len(s) != 0:
		a = max(s)
		for j in range(len(s)):
			if s[j] == a:
				var = 1
				ind = j
		col = col + [c[ind]]
		s = s[ind + 1:]
		c = c[ind + 1:]
	col.sort()
	for j in range(len(col) - 1):
		if col[j] != col[j + 1]:
			count += 1
	print(count)


import sys

def _int():
	return int(sys.stdin.readline())

def _ints():
	return map(int, sys.stdin.readline().split())

def _intarr():
	return list(map(int, sys.stdin.readline().split()))

def _str():
	return sys.stdin.readline()

def _strarr():
	return sys.stdin.readline().split()
t = _int()
ans = []
for _ in range(t):
	(n, m) = _ints()
	h = _intarr()
	c = _intarr()
	s = []
	for i in range(n):
		if len(s) == 0:
			s.append(i)
		else:
			while len(s) > 0:
				l = len(s)
				if h[s[l - 1]] <= h[i]:
					s.pop()
				else:
					break
			if len(s) == 0:
				s.append(i)
			elif c[s[len(s) - 1]] != c[i]:
				s.append(i)
	c_eff = set()
	for i in s:
		c_eff.add(c[i])
	ans.append(len(c_eff))
for a in ans:
	print(a)


from collections import defaultdict
for _ in range(int(input())):
	d = defaultdict(int)
	(n, m) = map(int, input().split())
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	l = [(h[i], c[i]) for i in range(n)]
	cnt = 1
	d[l[n - 1][1]] = 1
	h = l[n - 1][0]
	for i in range(n - 1, -1, -1):
		if l[i][0] > h:
			if not d[l[i][1]]:
				cnt += 1
			d[l[i][1]] = 1
			h = l[i][0]
	print(cnt)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mx = a[-1]
	s = set()
	s.add(b[-1])
	for i in range(n - 2, -1, -1):
		if a[i] > mx:
			mx = a[i]
			s.add(b[i])
	print(len(s))


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	m = a[-1]
	l = [b[-1]]
	for i in range(n - 1, -1, -1):
		if a[i] > m:
			m = a[i]
			l.append(b[i])
	s = list(set(l))
	print(len(s))


a = int(input())
for i in range(a):
	bb = list(map(int, input().split()))
	cc = list(map(int, input().split()))
	dd = list(map(int, input().split()))
	crr = []
	for i in range(len(cc)):
		while crr != [] and crr[-1][0] <= cc[i]:
			crr.pop()
		crr.append((cc[i], dd[i]))
	crr = sorted(crr, key=lambda x: x[1])
	if crr == []:
		print(0)
	else:
		count = 1
		for i in range(1, len(crr)):
			if crr[i][1] == crr[i - 1][1]:
				continue
			else:
				count += 1
		print(count)


t = int(input())
for _ in range(t):
	(n, m) = [int(v) for v in input().strip().split()]
	aN = [int(v) for v in input().strip().split()]
	aM = [int(v) for v in input().strip().split()]
	mN = max(aN)
	ind = n - aN[::-1].index(mN) - 1
	latest = aN[-1]
	indC = n - 1
	c = [aM[-1]]
	while indC > ind:
		if aN[indC - 1] > latest:
			if aM[indC - 1] in c:
				latest = aN[indC - 1]
			else:
				latest = aN[indC - 1]
				c.append(aM[indC - 1])
		indC -= 1
	print(len(c))


t = int(input())
for _ in range(t):
	(n, m) = [int(v) for v in input().strip().split()]
	arrN = [int(v) for v in input().strip().split()]
	arrM = [int(v) for v in input().strip().split()]
	maxN = max(arrN)
	index = n - arrN[::-1].index(maxN) - 1
	latest = arrN[-1]
	indexC = n - 1
	col = [arrM[-1]]
	while indexC > index:
		if arrN[indexC - 1] > latest:
			if arrM[indexC - 1] in col:
				latest = arrN[indexC - 1]
			else:
				latest = arrN[indexC - 1]
				col.append(arrM[indexC - 1])
		indexC -= 1
	print(len(col))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	height = list(map(int, input().split()))
	color = list(map(int, input().split()))
	max = height[n - 1]
	col = color[n - 1]
	wall = [col]
	for j in range(n - 2, -1, -1):
		if height[j] > max:
			max = height[j]
			col = color[j]
			wall.append(col)
	traverse = []
	for entry in wall:
		if entry not in traverse:
			traverse.append(entry)
	print(len(traverse))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	cnt = []
	for i in range(n):
		flag = True
		for j in range(i + 1, n):
			if h[j] >= h[i]:
				flag = False
				break
		if flag:
			cnt.append(c[i])
	print(len(set(cnt)))


class Stack:

	def __init__(self):
		self.stack = []
		self.top = -1

	def push(self, item, color):
		self.top += 1
		self.stack.append([item, color])
		return True

	def pop(self):
		if self.top == -1:
			return
		else:
			self.top -= 1
			return self.stack.pop()

	def peek(self):
		if self.top == -1:
			return
		else:
			return self.stack[self.top]

	def isempty(self):
		if self.top == -1:
			return True
		else:
			return False

	def display(self):
		for i in range(0, self.top + 1):
			print(self.stack[i], end=' ')
		print()
t = int(input())
while t:
	s = Stack()
	k = list(map(int, input().split()))
	height = list(map(int, input().split()))
	color = list(map(int, input().split()))
	n = k[0]
	m = k[1]
	m += 1
	arr = [0] * m
	s.push(height[0], color[0])
	for i in range(1, n):
		if height[i] >= s.peek()[0]:
			while not s.isempty() and height[i] >= s.peek()[0]:
				s.pop()
			s.push(height[i], color[i])
		else:
			s.push(height[i], color[i])
	while not s.isempty():
		color = s.pop()
		arr[color[1]] = 1
	count = 0
	for i in range(1, m):
		if arr[i] == 1:
			count += 1
	print(count)
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	v = [h[0]]
	cv = [c[0]]
	for i in range(1, n):
		j = 0
		while j < len(v):
			if v[j] <= h[i]:
				break
			j += 1
		v = v[:j] + [h[i]]
		cv = cv[:j] + [c[i]]
	cv.sort()
	ctr = 1
	for i in range(1, len(cv)):
		if cv[i - 1] != cv[i]:
			ctr += 1
	print(ctr)


for _ in range(int(input())):
	(n, _) = map(int, input().split())
	n -= 2
	heights = list(map(int, input().split()))
	colors = list(map(int, input().split()))
	last = heights[-1]
	count = {colors[-1]: 1}
	while n > -1:
		if last < heights[n]:
			last = heights[n]
			count[colors[n]] = 1
		n -= 1
	print(len(count))


for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	height = list(map(int, input().strip().split()))
	color = list(map(int, input().strip().split()))
	ans_colors = set()
	index = 0
	while True:
		max_height = max(height)
		slicer = len(height) - height[::-1].index(max_height)
		index = index + slicer
		ans_colors.add(color[index - 1])
		if slicer == len(height):
			break
		else:
			height = height[slicer:]
	print(len(ans_colors))


from functools import reduce as rd
import operator as optr
import math
import itertools
inp = lambda : map(int, input().split())
for __ in range(int(input())):
	(n, m) = inp()
	h = list(inp())
	col = list(inp())
	color = set()
	check = 0
	i = n - 1
	while i >= 0:
		if h[i] > check:
			check = h[i]
			color.add(col[i])
		i -= 1
	print(len(color))


for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	heights = list(map(int, input().strip().split()))
	colors = list(map(int, input().strip().split()))
	pairs = list(zip(heights, colors))
	if n == 1:
		print(1)
		continue
	current = n - 1
	index = n - 2
	while index > -1:
		if heights[current] >= heights[index]:
			heights[index] = -1
			colors[index] = -1
		else:
			current = index
		index -= 1
	cache = {x: 1 for x in colors if x != -1}
	print(len(cache.keys()))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	own = []
	for i in range(n):
		H = h[i]
		C = c[i]
		hello = []
		for j in own:
			if H < j[0]:
				hello.append(j)
		own = hello
		own.append((H, C))
	my = set()
	for i in own:
		my.add(i[1])
	print(len(my))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	top = 0
	col = set()
	ref = []
	for i in range(n - 1, 0, -1):
		if h[i] > top:
			top = h[i]
			col.add(c[i])
	if h[0] > top:
		col.add(c[0])
	print(len(col))


import math as ma
import sys
from sys import exit
from decimal import Decimal as dec
from itertools import permutations

def li():
	return list(map(int, sys.stdin.readline().split()))

def num():
	return map(int, sys.stdin.readline().split())

def nu():
	return int(sys.stdin.readline())

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = nu()
for it in range(t):
	(n, m) = num()
	a = li()
	c = li()
	z = [0] * n
	pp = [0] * n
	pp[n - 1] = a[n - 1]
	for i in range(n - 2, -1, -1):
		pp[i] = max(a[i + 1], pp[i + 1])
	sq = set()
	for i in range(0, n - 1):
		if a[i] <= pp[i]:
			continue
		sq.add(c[i])
	sq.add(c[n - 1])
	print(len(sq))


from sys import stdin, stdout
import cProfile, math
from collections import Counter
from bisect import bisect_left
import itertools
from copy import deepcopy
from fractions import Fraction
printHeap = str()
memory_constrained = False
N = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10000000)

class Operation:

	def __init__(self, name, function, function_on_equal, neutral_value=0):
		self.name = name
		self.f = function
		self.f_on_equal = function_on_equal

def add_multiple(x, count):
	return x * count

def min_multiple(x, count):
	return x

def max_multiple(x, count):
	return x
sum_operation = Operation('sum', sum, add_multiple, 0)
min_operation = Operation('min', min, min_multiple, 1000000000.0)
max_operation = Operation('max', max, max_multiple, -1000000000.0)

class SegmentTree:

	def __init__(self, array, operations=[sum_operation, min_operation, max_operation]):
		self.array = array
		if type(operations) != list:
			raise TypeError('operations must be a list')
		self.operations = {}
		for op in operations:
			self.operations[op.name] = op
		self.root = SegmentTreeNode(0, len(array) - 1, self)

	def query(self, start, end, operation_name):
		if self.operations.get(operation_name) == None:
			raise Exception('This operation is not available')
		return self.root._query(start, end, self.operations[operation_name])

	def summary(self):
		return self.root.values

	def update(self, position, value):
		self.root._update(position, value)

	def update_range(self, start, end, value):
		self.root._update_range(start, end, value)

	def __repr__(self):
		return self.root.__repr__()

class SegmentTreeNode:

	def __init__(self, start, end, segment_tree):
		self.range = (start, end)
		self.parent_tree = segment_tree
		self.range_value = None
		self.values = {}
		self.left = None
		self.right = None
		if start == end:
			self._sync()
			return
		self.left = SegmentTreeNode(start, start + (end - start) // 2, segment_tree)
		self.right = SegmentTreeNode(start + (end - start) // 2 + 1, end, segment_tree)
		self._sync()

	def _query(self, start, end, operation):
		if end < self.range[0] or start > self.range[1]:
			return None
		if start <= self.range[0] and self.range[1] <= end:
			return self.values[operation.name]
		self._push()
		left_res = self.left._query(start, end, operation) if self.left else None
		right_res = self.right._query(start, end, operation) if self.right else None
		if left_res is None:
			return right_res
		if right_res is None:
			return left_res
		return operation.f([left_res, right_res])

	def _update(self, position, value):
		if position < self.range[0] or position > self.range[1]:
			return
		if position == self.range[0] and self.range[1] == position:
			self.parent_tree.array[position] = value
			self._sync()
			return
		self._push()
		self.left._update(position, value)
		self.right._update(position, value)
		self._sync()

	def _update_range(self, start, end, value):
		if end < self.range[0] or start > self.range[1]:
			return
		if start <= self.range[0] and self.range[1] <= end:
			self.range_value = value
			self._sync()
			return
		self._push()
		self.left._update_range(start, end, value)
		self.right._update_range(start, end, value)
		self._sync()

	def _sync(self):
		if self.range[0] == self.range[1]:
			for op in self.parent_tree.operations.values():
				current_value = self.parent_tree.array[self.range[0]]
				if self.range_value is not None:
					current_value = self.range_value
				self.values[op.name] = op.f([current_value])
		else:
			for op in self.parent_tree.operations.values():
				result = op.f([self.left.values[op.name], self.right.values[op.name]])
				if self.range_value is not None:
					bound_length = self.range[1] - self.range[0] + 1
					result = op.f_on_equal(self.range_value, bound_length)
				self.values[op.name] = result

	def _push(self):
		if self.range_value is None:
			return
		if self.left:
			self.left.range_value = self.range_value
			self.right.range_value = self.range_value
			self.left._sync()
			self.right._sync()
			self.range_value = None

	def __repr__(self):
		ans = '({}, {}): {}\n'.format(self.range[0], self.range[1], self.values)
		if self.left:
			ans += self.left.__repr__()
		if self.right:
			ans += self.right.__repr__()
		return ans

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def primeFactors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

def isprime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def test_print(*args):
	if test:
		print(args)

def display_list(list1, sep=' '):
	stdout.write(sep.join(map(str, list1)) + '\n')

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result
TestCases = True
test = False

def main():
	(n, m) = get_tuple()
	heights = get_list()
	colors = get_list()
	li = list()
	for i in range(n):
		while len(li) > 0 and li[-1][0] <= heights[i]:
			li.pop()
		li.append([heights[i], colors[i]])
	hi = [x[0] for x in li]
	ci = [x[1] for x in li]
	print(len(set(ci)))
if TestCases:
	for _ in range(get_int()):
		cProfile.run('main()') if test else main()
else:
	cProfile.run('main()') if test else main()


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	distinct_color = {}
	(f, ans) = (0, 0)
	for i in range(n):
		for j in range(i - 1, -1, -1):
			if a[j] > a[i]:
				break
			else:
				a[j] = 0
	for i in range(n):
		if a[i] != 0:
			if not distinct_color.get(b[i]):
				distinct_color[b[i]] = 1
	print(len(distinct_color))


testcase = int(input())
while testcase:
	testcase -= 1
	(n, m) = [int(x) for x in input().strip().split()]
	h = [int(x) for x in input().strip().split()]
	c = [int(x) for x in input().strip().split()]
	h = h[::-1]
	c = c[::-1]
	mi = h[0]
	q = c[0]
	t = 1
	col = [c[0]]
	for i in range(1, n):
		if h[i] > mi:
			if c[i] != q:
				col.append(c[i])
				q = c[i]
				mi = h[i]
				t += 1
			elif c[i] == q:
				mi = h[i]
	print(len(set(col)))


T = int(input())
for i in range(0, T):
	(N, M) = map(int, input().split())
	H = list(map(int, input().split()))
	C = list(map(int, input().split()))
	difcol = 1
	color = [0] * N
	color[0] = C[0]
	for j in range(1, N):
		if H[j] < H[j - 1]:
			color[j] = C[j]
		else:
			for k in range(j - 1, -1, -1):
				if H[k] > H[j]:
					break
				else:
					color[k] = C[j]
	set1 = set(color)
	set1.discard(0)
	print(len(set1))


def fun():
	test = int(input())
	for i in range(test):
		(n, k) = map(int, input().split())
		h = list(map(int, input().split()))
		c = list(map(int, input().split()))
		occ = dict()
		for i in range(n):
			occ[h[i]] = occ.get(h[i], 0) + 1
		maxi = [0] * (n + 1)
		for i in range(n - 1, -1, -1):
			maxi[i] = max(maxi[i + 1], h[i])
		ans_ind = []
		j = 0
		d = dict()
		for i in range(n):
			if h[i] == maxi[i]:
				d[h[i]] = d.get(h[i], 0) + 1
				if d[h[i]] == occ[h[i]]:
					ans_ind.append(i)
					j += 1
				else:
					j += 1
			else:
				occ[h[i]] -= 1
		used = [0] * (k + 1)
		for i in ans_ind:
			used[c[i]] = 1
		print(sum(used))
fun()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	cl = list()
	hl = list()
	for j in range(n):
		while hl != [] and h[j] >= hl[-1]:
			hl.pop()
			cl.pop()
		hl.append(h[j])
		cl.append(c[j])
	s = set(cl)
	print(len(s))


T = int(input())
while T:
	(N, M) = list(map(int, input().split()))
	heights = list(map(int, input().split()))
	colors = list(map(int, input().split()))
	curr_max_height = heights[N - 1]
	distinct_colors = set()
	distinct_colors.add(colors[N - 1])
	count = 1
	for i in reversed(range(N - 1)):
		if heights[i] > curr_max_height:
			if colors[i] not in distinct_colors:
				distinct_colors.add(colors[i])
				count += 1
			curr_max_height = heights[i]
	print(count)
	T -= 1


from collections import defaultdict as dd

def default():
	return 0
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	li = [0]
	for i in range(1, n):
		done = False
		for (pos, ind) in enumerate(li):
			if h[ind] <= h[i]:
				li = li[:pos] + [i]
				done = True
				break
		if not done:
			li = li + [i]
	prev = li[0]
	color = c[prev]
	count = 1
	seen = dd(default)
	seen[color] = 1
	for ind in li[1:]:
		col = c[ind]
		if col != color:
			color = col
			if not seen[col]:
				seen[col] = 1
				count += 1
	print(count)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.reverse()
	maxi = a[0]
	b.reverse()
	l = [b[0]]
	for i in range(len(b)):
		if a[i] > maxi:
			maxi = a[i]
			l.append(b[i])
	l = list(set(l))
	print(len(l))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	arr1 = [int(i) for i in input().split()]
	arr2 = [int(i) for i in input().split()]
	ll = []
	col = []
	for i in range(len(arr1)):
		if i == 0:
			ll.append(arr1[i])
			col.append(arr2[i])
		elif min(ll) > arr1[i]:
			if arr2[i] not in col:
				col.append(arr2[i])
				ll.append(arr1[i])
		else:
			while len(ll) > 0 and min(ll) <= arr1[i]:
				col.remove(col[ll.index(min(ll))])
				ll.remove(min(ll))
			if arr2[i] not in col:
				col.append(arr2[i])
				ll.append(arr1[i])
	print(len(col))


from bisect import bisect_left
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	(a, cl, l) = ([], [], 0)
	for i in range(n):
		if i == 0:
			a.append(h[i])
			cl.append(c[i])
			l += 1
		elif a[l - 1] <= h[i]:
			while l > 0 and a[l - 1] <= h[i]:
				a.pop()
				cl.pop()
				l -= 1
			a.append(h[i])
			cl.append(c[i])
			l += 1
		else:
			a.append(h[i])
			cl.append(c[i])
			l += 1
	print(len(set(cl)))


t = int(input())
for _ in range(t):
	(n, m) = tuple(map(int, input().split()))
	ar1 = list(map(int, input().split()))
	ar2 = list(map(int, input().split()))
	s = set()
	s.add(ar2[n - 1])
	k = ar1[n - 1]
	for i in range(n - 2, -1, -1):
		if ar1[i] > k:
			k = ar1[i]
			s.add(ar2[i])
	print(len(s))


t = int(input())
for j in range(t):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	for i in range(m + 1):
		c.append(0)
	c[b[n - 1]] = 1
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			k = a[i]
			continue
		if a[i] > k:
			c[b[i]] += 1
			k = a[i]
	cou = 0
	for i in range(m + 1):
		if c[i] > 0:
			cou = cou + 1
	print(cou)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	h = list(map(int, input().split()))
	c = list(map(int, input().split()))
	h = h[::-1]
	c = c[::-1]
	hmax = max(h)
	ha = []
	ha.append(h[0])
	check = max(ha)
	count = 1
	ca = []
	ca.append(c[0])
	for j in range(1, n):
		if hmax in ha:
			break
		if h[j] > check:
			ha.append(h[j])
			if c[j] not in ca:
				count = count + 1
				ca.append(c[j])
		check = max(ha)
	print(count)


T = int(input())
for q in range(T):
	(n, m) = map(int, input().strip().split())
	hei = list(map(int, input().strip().split()))
	colo = list(map(int, input().strip().split()))
	ans = 0
	arr = []
	c = 1
	k = hei[n - 1]
	ind = [colo[n - 1]]
	for i in range(n - 1, -1, -1):
		if hei[i] > k:
			c += 1
			k = hei[i]
			ind.append(colo[i])
	mp = {}
	ans = 0
	for i in range(len(ind)):
		if ind[i] not in mp:
			ans += 1
			mp[ind[i]] = 1
	print(ans)


import sys
sys.setrecursionlimit(100000)

def check(h, c, count, pv, dict):
	m = max(h)
	for k in range(len(h) - 1, -1, -1):
		if h[k] == m:
			break
	if count == 0:
		pv = c[k]
		count = count + 1
		dict[c[k]] = 1
	elif c[k] != pv and dict[c[k]] == 0:
		count = count + 1
		pv = c[k]
		dict[c[k]] = 1
	h = h[k + 1:len(h)]
	c = c[k + 1:len(c)]
	if h == []:
		return count
	else:
		return check(h, c, count, pv, dict)
t = int(input())
for i in range(0, t):
	s = input()
	s = list(map(int, s.split()))
	n = s[0]
	m = s[1]
	h = input()
	h = list(map(int, h.split()))
	c = input()
	c = list(map(int, c.split()))
	dict = {}
	for j in range(1, m + 1):
		dict[j] = 0
	print(check(h, c, 0, 0, dict))


t = int(input())
while t:
	(n, m) = [int(i) for i in input().split()]
	h = [int(i) for i in input().split()]
	c = [int(i) for i in input().split()]
	z = list(set(c))
	if len(z) == 1:
		print(1)
		t -= 1
		continue
	max = len(z)
	i = 1
	while i < n:
		j = i - 1
		while j >= 0:
			if c[j] != 0:
				if h[i] >= h[j]:
					c[j] = 0
				else:
					break
			j -= 1
		i += 1
	new = list(set(c))
	if 0 in new:
		print(len(new) - 1)
	else:
		print(len(new))
	t -= 1


t = int(input())
for i in range(t):
	lis0 = list(map(int, input().split()))
	n = lis0[0]
	m = lis0[1]
	ct = 0
	lis1 = list(map(int, input().split()))
	lis2 = list(map(int, input().split()))
	cmp = lis1[n - 1]
	lis3 = []
	lis3.append(lis2[n - 1])
	for j in range(n - 1):
		if lis1[n - 2 - j] > cmp:
			lis3.append(lis2[n - 2 - j])
			cmp = lis1[n - 2 - j]
	lis3.sort()
	for k in range(len(lis3) - 1):
		if lis3[k] == lis3[k + 1]:
			ct += 1
	print(len(lis3) - ct)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	k = list(map(int, input().split()))
	c = l[-1]
	x = [c]
	for j in l[-2:0:-1]:
		c = max(c, j)
		x.append(c)
	x.reverse()
	d = []
	for j in range(n - 1):
		if l[j] > x[j]:
			d.append(k[j])
	d.append(k[-1])
	print(len(set(d)))