Read problems statements in Mandarin Chinese  and Russian. 

Haku has been newly hired by Chef to clean tables at his restaurant. So whenever a customer wants a table, Haku must clean it.
But Haku happens to be a lazy boy. So in the morning, when the restaurant is opened, all the tables are dirty from night before.
The customer don't leave the table unless they are politely requested to do so. And customers can order meal later again. So if they were already having a table, they can be served on the same table [Haku doesn't have to clean :)]. But if they don't have a table then they must be given some table [Haku must clean :(]
The restaurant has N tables. When a customer requires a table, he/she can occupy any unoccupied table. However if all tables are occupied, then Haku is free to ask politely any customer to leave his/her table. And the freed table can be given to the waiting customer.
Now Chef has the psychic ability to tell the order of customer meal requests for the entire day. Given this list, help Haku find the minimum number of times he has to clean the tables.

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

First line contains integer T, number of test cases.
First line of each test case contains 2 integers N, number of tables and M, number of customer orders. Followed by M integers on next line, which is the order in which customers ask for meal. Customers are referenced by integer C.

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

For each test case output the minimum number of times Haku must clean the table(s).

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 200$
$1 ≤ M ≤ 400$
$1 ≤ C ≤ 400$

----- Sample Input 1 ------ 
4
2 4
1 2 3 4
3 2
4 1
3 6
1 2 1 3 4 1
3 5
1 2 1 3 4
----- Sample Output 1 ------ 
4
2
4
4
----- explanation 1 ------ 
Example case 1. In the starting all tables i.e. 2 tables are unoccupied. When customer 1 asks for table, he can be given any of the 2 tables. Haku has to clean either of the table. Next customer 2 can occupy the other free table. Haku must clean second time. When customer 3 comes Haku can ask either customer 1 or 2 to leave. Suppose he asks customer 1 to leave. Then he has to clean table for the third time. When customer 4 comes, Haku can ask customer 2 or 3 to leave. In either case Haku will have to clean the table for the fourth time. Phew!!
Example case 4. Suppose the tables are listed as [-, -, -]. A possible optimal order of allocating tables can be [1, -, -] -> [1, 2, -] -> [1, 2, -] -> [1, 2, 3] -> [4, 2, 3]. So Haku will have to clean table for order no. 1, 2, 4 and 5. That is 4 times.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Data structures

Implementation


Solutions:
from collections import Counter
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	orders = list(map(int, input().split()))
	tables = set()
	oper = 0
	for (k, i) in enumerate(orders):
		if i in tables:
			continue
		oper += 1
		if len(tables) < n:
			tables.add(i)
			continue
		tmp = tables.copy()
		for j in range(k + 1, m):
			if len(tmp) == 1:
				break
			if orders[j] in tmp:
				tmp.remove(orders[j])
		tables.remove(tmp.pop())
		tables.add(i)
	print(oper)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	order = list(map(int, input().split()))
	table = []
	count = 0
	for i in range(m):
		if order[i] in table:
			continue
		count = count + 1
		if len(table) < n:
			table.append(order[i])
			continue
		unique = set(table)
		for j in range(i + 1, m):
			if len(unique) == 1:
				break
			if order[j] in unique:
				unique.remove(order[j])
		first = list(unique)[0]
		table.remove(first)
		table.append(order[i])
	print(count)
	t = t - 1


t = int(input())
for i in range(t):
	(a, n) = map(int, input().split())
	l = list(map(int, input().split()))
	k = []
	v = 0
	for j in range(n):
		if l[j] in k:
			continue
		v += 1
		if len(k) < a:
			k.append(l[j])
			continue
		x = set(k)
		for z in range(j + 1, n):
			if len(x) == 1:
				break
			if l[z] in x:
				x.remove(l[z])
		m = list(x)[0]
		k.remove(m)
		k.append(l[j])
	print(v)


from queue import Queue
t = int(input())
while t:
	(n, m) = map(int, input().split())
	orders = list(map(int, input().split()))
	cin = [-1 for num in range(401)]
	d = {}
	for ele in orders:
		if ele not in d:
			d[ele] = 1
		else:
			d[ele] += 1
	tables = 0
	clean = 0
	q = Queue()
	for k in range(len(orders)):
		if cin[orders[k]] == 1:
			d[orders[k]] -= 1
			if d[orders[k]] <= 0:
				q.put(orders[k])
			continue
		elif tables < n:
			cin[orders[k]] = 1
			tables += 1
			clean += 1
			d[orders[k]] -= 1
			if d[orders[k]] <= 0:
				q.put(orders[k])
		elif q.empty() == 1 and k <= m - 2:
			temp = []
			for j in range(k + 1, m):
				if cin[orders[j]] == 1 and orders[j] not in temp:
					temp.append(orders[j])
			cin[temp[-1]] = -1
			cin[orders[k]] = 1
			clean += 1
			d[orders[k]] -= 1
			if d[orders[k]] <= 0:
				q.put(orders[k])
		elif q.empty() == 1 and k == m - 1:
			clean += 1
		else:
			ele = q.get()
			cin[ele] = -1
			cin[orders[k]] = 1
			clean += 1
			d[orders[k]] -= 1
			if d[orders[k]] <= 0:
				q.put(orders[k])
	print(clean)
	t -= 1


from tkinter import Y
Y = int(input())
for i in range(Y):
	(a, n) = map(int, input().split())
	l = list(map(int, input().split()))
	k = []
	b = 0
	for j in range(n):
		if l[j] in k:
			continue
		b += 1
		if len(k) < a:
			k.append(l[j])
			continue
		x = set(k)
		for z in range(j + 1, n):
			if len(x) == 1:
				break
			if l[z] in x:
				x.remove(l[z])
		m = list(x)[0]
		k.remove(m)
		k.append(l[j])
	print(b)


t = int(input())
while t > 0:
	t -= 1
	(a, n) = map(int, input().split())
	arr = list(map(int, input().split()))
	mk = []
	v = 0
	for i in range(n):
		if arr[i] in mk:
			continue
		v += 1
		if len(mk) < a:
			mk.append(arr[i])
			continue
		k = set(mk)
		for j in range(i + 1, n):
			if len(k) == 1:
				break
			if arr[j] in k:
				k.remove(arr[j])
		m = list(k)[0]
		mk.remove(m)
		mk.append(arr[i])
	print(v)


from collections import defaultdict

class Table:

	def __init__(self, n, pos):
		self.table = set()
		self.pos = pos
		self.n = n

	def is_full(self):
		return len(self.table) == self.n

	def insert(self, k):
		self.table.add(k)

	def exists(self, k):
		return k in self.table

	def evict(self):
		mmax = -1
		to_remove = -1
		for t in self.table:
			if not self.pos[t]:
				mmax = 10000000000
				to_remove = t
				break
			elif self.pos[t][0] > mmax:
				mmax = self.pos[t][0]
				to_remove = t
		if mmax == -1:
			to_remove = next(iter(self.table))
		self.table.remove(to_remove)

	def remove_entry(self, k):
		self.pos[k].pop(0)

def doit(n, ar):
	pos = defaultdict(list)
	for (i, a) in enumerate(ar):
		pos[a].append(i)
	table = Table(n, pos)
	cleaned = 0
	for (i, a) in enumerate(ar):
		if table.exists(a):
			pass
		elif not table.is_full():
			table.insert(a)
			cleaned += 1
		else:
			table.evict()
			table.insert(a)
			cleaned += 1
		table.remove_entry(a)
	print(cleaned)

def solve():
	for _ in range(int(input())):
		(n, _) = (int(i) for i in input().split())
		ar = [int(i) for i in input().split()]
		doit(n, ar)
solve()


from collections import defaultdict

def get_farthest_customer(allocation, request):
	max_distance = -1
	farthest_c = -1
	for c in allocation:
		if len(request[c]) == 0:
			return c
		elif request[c][0] > max_distance:
			farthest_c = c
			max_distance = request[c][0]
	return farthest_c
T = int(input())
output = []
for _ in range(T):
	(N, M) = [int(x) for x in input().split()]
	array = [int(x) for x in input().split()]
	request = defaultdict(list)
	for i in range(M):
		request[array[i]].append(i)
	tables = [x for x in range(N)]
	allocation = {}
	clean = 0
	for c in array:
		if c in allocation:
			request[c].pop(0)
			continue
		elif len(tables) > 0:
			tab = tables.pop()
			clean += 1
			allocation[c] = tab
			request[c].pop(0)
		else:
			farthest_c = get_farthest_customer(allocation, request)
			tab = allocation[farthest_c]
			clean += 1
			del allocation[farthest_c]
			allocation[c] = tab
			request[c].pop(0)
	output.append(clean)
for o in output:
	print(o)


T = int(input())
for i in range(T):
	(a, n) = map(int, input().split())
	arr = list(map(int, input().split()))
	mk = dict()
	s = 0
	v = 0
	for i in range(n):
		p = arr[i]
		if p in mk:
			continue
		elif s < a:
			mk[p] = 1
			s += 1
			v += 1
		elif s == a:
			k = set(mk.keys())
			m = arr[i]
			for j in range(i + 1, n):
				if arr[j] in k:
					k.remove(arr[j])
					m = arr[j]
			if len(k) != 0:
				m = k.pop()
			del mk[m]
			mk[p] = 1
			v += 1
	print(v)


t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	order = list(map(int, input().split()))
	a = []
	cleaning = 0
	for i in range(m):
		if len(a) >= 1 and order[i] in a:
			continue
		cleaning += 1
		if len(a) < n:
			a.append(order[i])
			continue
		temp = set(a)
		for j in range(i + 1, m):
			if len(temp) == 1:
				break
			if order[j] in temp:
				temp.remove(order[j])
		a.remove(list(temp)[0])
		a.append(order[i])
	print(cleaning)


t = int(input())
while t > 0:
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	c = input().split()
	s = set()
	count = 0
	l = []
	for i in range(m):
		c[i] = int(c[i])
	for i in range(m):
		if c[i] in l:
			continue
		count += 1
		if len(l) < n:
			l.append(c[i])
			continue
		temp = list(l)
		for j in range(i + 1, m):
			if len(temp) == 1:
				break
			if c[j] in temp:
				temp.remove(c[j])
		l.remove(temp[0])
		l.append(c[i])
	print(count)
	t -= 1


answers = []

def solve(N, M, orders):
	store = {}
	for (i, order) in enumerate(orders):
		if order not in store:
			store[order] = [i]
		else:
			store[order].append(i)
	trackStore = {}
	final = 0
	for (i, order) in enumerate(orders):
		if len(trackStore) == N and order not in trackStore:
			temp = []
			flag = 1
			for ele in trackStore:
				if len(store[ele]) == 0:
					del trackStore[ele]
					flag = 0
					break
				for j in store[ele]:
					if j > i:
						temp.append(j)
						break
			if flag == 1:
				del trackStore[orders[max(temp)]]
		if order not in trackStore:
			trackStore[order] = 1
			final += 1
		store[order].pop(0)
	answers.append(final)
T = int(input())
while T:
	(N, M) = [int(x) for x in input().split()]
	orders = [int(x) for x in input().split()]
	solve(N, M, orders)
	T -= 1
for ans in answers:
	print(ans)


answers = []

def solve(N, M, orders):
	store = {}
	for (i, order) in enumerate(orders):
		if order not in store:
			store[order] = {'total': 1, 'last': [i]}
		else:
			store[order]['total'] += 1
			store[order]['last'].append(i)
	trackSet = set()
	final = 0
	for (i, order) in enumerate(orders):
		if len(trackSet) == N and order not in trackSet:
			temp = []
			flag = 1
			for ele in trackSet:
				if store[ele]['total'] == 0:
					trackSet.discard(ele)
					flag = 0
					break
				for j in store[ele]['last']:
					if j > i:
						temp.append(j)
						break
			if flag == 1:
				trackSet.discard(orders[max(temp)])
		if order not in trackSet:
			trackSet.add(order)
			final += 1
		store[order]['total'] -= 1
	answers.append(final)
T = int(input())
while T:
	(N, M) = [int(x) for x in input().split()]
	orders = [int(x) for x in input().split()]
	solve(N, M, orders)
	T -= 1
for ans in answers:
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	orders = list(map(int, input().strip().split()))
	custmap = {}
	for (index, order) in enumerate(orders):
		if order not in custmap:
			custmap[order] = {'total': 1, 'last': [index]}
		else:
			custmap[order]['total'] += 1
			custmap[order]['last'].append(index)
	ocust = set()
	ans = 0
	for (index, order) in enumerate(orders):
		if len(ocust) == n and order not in ocust:
			temp = []
			flag = True
			for c in ocust:
				if custmap[c]['total'] == 0:
					flag = False
					ocust.discard(c)
					break
				for j in custmap[c]['last']:
					if j > index:
						temp.append(j)
						break
			if flag:
				ocust.discard(orders[max(temp)])
		if order not in ocust:
			ocust.add(order)
			ans += 1
		custmap[order]['total'] -= 1
	print(ans)


from math import gcd
import sys
from heapq import heappush, heappop
from collections import Counter, defaultdict, deque
input = lambda : sys.stdin.readline().strip()
c = lambda x: 10 ** 9 if x == '?' else int(x)

class node:

	def __init__(self, x, y):
		self.a = [x, y]

	def __lt__(self, b):
		return b.a[0] < self.a[0]

	def __repr__(self):
		return str(self.a[0]) + ' ' + str(self.a[1])

def main():
	for _ in range(int(input())):
		heap = []
		(n, m) = list(map(int, input().split()))
		a = list(map(int, input().split()))
		d = defaultdict(lambda : deque([]))
		for i in range(m):
			d[a[i]].append(i)
		for i in d:
			d[i].append(m)
		l = []
		s = set()
		saaf = 0
		for i in range(m):
			if len(s) >= n and a[i] not in s:
				a1 = max(l, key=lambda x: d[x][0])
				l.remove(a1)
				l.append(a[i])
				s.discard(a1)
				s.add(a[i])
				d[a[i]].popleft()
				saaf += 1
			elif len(s) >= n and a[i] in s:
				d[a[i]].popleft()
			elif len(s) < n and a[i] not in s:
				l.append(a[i])
				d[a[i]].popleft()
				s.add(a[i])
				saaf += 1
			elif len(s) < n and a[i] in s:
				d[a[i]].popleft()
		print(saaf)
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	tab = set()
	for i in range(m):
		if a[i] in tab:
			continue
		if len(tab) < n:
			tab.add(a[i])
			ans += 1
			continue
		x = set()
		for j in range(i + 1, m):
			if a[j] in tab and len(x) < n - 1:
				x.add(a[j])
		tab = x
		tab.add(a[i])
		ans += 1
	print(ans)


try:
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		memory = list(map(int, input().split()))
		space = [0] * N
		count = 0
		i = -1
		for item in memory:
			bits = [1000] * N
			i += 1
			if item in space:
				continue
			else:
				count += 1
				if 0 in space:
					it = space.index(0)
					space[it] = item
				else:
					for j in range(i + 1, len(memory)):
						if memory[j] in space:
							ii = space.index(memory[j])
							if bits[ii] == 1000:
								bits[ii] = j
					replaceable = max(bits)
					if replaceable != 1000:
						r_index = bits.index(replaceable)
						space[r_index] = item
					else:
						space[bits.index(1000)] = item
		print(count)
except:
	pass


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	l = []
	ans = 0
	w = 0
	for i in range(len(a)):
		if len(l) != n:
			if a[i] not in l:
				l.append(a[i])
				ans += 1
		elif a[i] not in l:
			m = 0
			for j in range(len(l)):
				if l[j] in a[i + 1:]:
					m = max(m, a[i + 1:].index(l[j]))
					w = 1
				else:
					l[j] = a[i]
					ans += 1
					w = 0
					break
			if w == 1:
				c = 0
				c = a[i + 1:][m]
				h = 0
				h = l.index(c)
				l[h] = a[i]
				ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	order = list(map(int, input().split()))
	table = []
	ans = 0
	tcount = 0
	for i in range(m):
		if order[i] in table:
			continue
		ans += 1
		if tcount < n:
			table += (order[i],)
			tcount += 1
			continue
		tmp = set(table)
		for j in range(i + 1, m):
			if len(tmp) == 1:
				break
			elif order[j] in tmp:
				tmp.remove(order[j])
		table.remove(list(tmp)[0])
		table += (order[i],)
	print(ans)


from typing import Iterable, Dict, Optional, Set

class CustomerState:

	def __init__(self, customer_id):
		self.__customer_id = customer_id
		self.__is_seated = False
		self.__order_ids = []

	def add_order(self, order_id: int):
		self.__order_ids.append(order_id)

	def remove_order(self):
		assert len(self.__order_ids) > 0, 'Attempted to remove orders from a customer with no orders left'
		self.__order_ids.pop(0)

	def seat(self):
		self.__is_seated = True

	def evict(self):
		self.__is_seated = False

	def is_seated(self) -> bool:
		return self.__is_seated

	def orders_left(self) -> int:
		return len(self.__order_ids)

	def customer_id(self) -> int:
		return self.__customer_id

	def earliest_next_reference(self) -> int:
		if len(self.__order_ids) > 0:
			return self.__order_ids[0]
		return -1

	def order_ids(self):
		return self.__order_ids

def calculate_clean_count(table_count: int, customer_orders: Iterable[int]) -> int:
	customer_states: Dict[CustomerState] = {}
	for i in range(0, len(customer_orders)):
		customer_id = customer_orders[i]
		if customer_id not in customer_states:
			customer_states[customer_id] = CustomerState(customer_id)
		customer_states[customer_id].add_order(i)
	seated_customers: Set[CustomerState] = set()
	clean_count = 0
	for customer_id in customer_orders:
		target_customer = customer_states[customer_id]
		if target_customer.is_seated():
			target_customer.remove_order()
			continue
		if len(seated_customers) != table_count:
			target_customer.seat()
			seated_customers.add(target_customer)
			clean_count += 1
			target_customer.remove_order()
			continue
		eviction_target: CustomerState = None
		for customer_state in seated_customers:
			if customer_state.orders_left() == 0:
				eviction_target = customer_state
				break
			if eviction_target is None or eviction_target.earliest_next_reference() < customer_state.earliest_next_reference():
				eviction_target = customer_state
		eviction_target.evict()
		seated_customers.remove(eviction_target)
		clean_count += 1
		target_customer.seat()
		seated_customers.add(target_customer)
		target_customer.remove_order()
	return clean_count
testcase_count = int(input())
for _ in range(0, testcase_count):
	(table_count, customer_order_count) = [int(number) for number in input().split(' ')]
	customer_orders = [int(number) for number in input().split(' ')]
	print(calculate_clean_count(table_count, customer_orders))


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l1 = []
	(ans, occupied) = (0, 0)
	for i in range(m):
		if l[i] not in l1:
			if occupied < n:
				l1.append(l[i])
				ans += 1
				occupied += 1
			else:
				(p, q) = (0, 0)
				for j in l1:
					flag = 0
					for k in range(i + 1, m):
						if l[k] == j:
							if k > p:
								p = k
								q = j
							flag = 1
							break
					if flag == 0:
						l1.remove(j)
						l1.append(l[i])
						ans += 1
						break
				if flag == 1:
					l1.remove(q)
					l1.append(l[i])
					ans += 1
	print(ans)


def farthest(tab_arr, arr, n):
	(x, y) = (-1, -1)
	for j in range(n):
		i = 0
		while arr[i] != tab_arr[j]:
			i += 1
		if i > x:
			x = i
			y = j
	return y

def count(tab_arr, arr, n):
	for i in range(n):
		if arr.count(tab_arr[i]) == 0:
			return i
	return -1
test = int(input())
for _ in range(test):
	(n, m) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	(i, tab, clean) = (0, 0, 0)
	curr = []
	while i < m:
		while tab < n and i < m:
			if arr[i] not in curr:
				curr.append(arr[i])
				tab += 1
				clean += 1
			i += 1
		if i == m:
			break
		while i < m:
			if arr[i] not in curr:
				break
			i += 1
		if i < m and count(curr, arr[i + 1:m], n) != -1:
			curr[count(curr, arr[i + 1:m], n)] = arr[i]
			clean += 1
			i += 1
		elif i < m:
			a = farthest(curr, arr[i + 1:m], n)
			curr[a] = arr[i]
			clean += 1
			i += 1
		else:
			break
	print(clean)


def farthest_page(tables, arr, i, m):
	val = dict()
	for cust in tables:
		dist = 0
		for j in range(i + 1, m):
			if arr[j] == cust:
				val[cust] = dist
				break
			dist += 1
	max_val = list(val.keys())[0]
	for cust in val.keys():
		if val[cust] > val[max_val]:
			max_val = cust
	return max_val

def solve(n, m, arr):
	seats_left = n
	clean = 0
	future = dict()
	tables = set()
	for cust in arr:
		if future.get(cust) == None:
			future[cust] = 1
		else:
			future[cust] += 1
	for i in range(0, m):
		cust = arr[i]
		future[cust] -= 1
		if cust in tables:
			continue
		if seats_left > 0:
			tables.add(cust)
			seats_left -= 1
			clean += 1
		elif seats_left == 0:
			found_replacement = -1
			for x in tables:
				if future[x] == 0:
					found_replacement = x
			if found_replacement == -1:
				found_replacement = farthest_page(tables, arr, i, m)
			tables.remove(found_replacement)
			tables.add(cust)
			clean += 1
	print(clean)
	return

def main():
	t = int(input())
	while t > 0:
		(n, m) = (int(i) for i in input().split())
		arr = [int(i) for i in input().split()]
		solve(n, m, arr)
		t -= 1
	return
main()


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	a = []
	s = 0
	for i in range(m):
		if l[i] not in a:
			s += 1
			if len(a) < n:
				a.append(l[i])
			else:
				k = a.copy()
				y = 0
				for j in range(i + 1, m):
					if l[j] in k:
						k.remove(l[j])
						y = l[j]
				if k == []:
					a.remove(y)
				else:
					a.remove(k[0])
				a.append(l[i])
	print(s)
	t -= 1


import sys
read = sys.stdin.readline
for i in range(int(read())):
	(t, no) = map(int, read().split())
	orders = list(map(int, read().split()))
	inres = []
	tablescleaned = 0
	for i in range(no):
		if len(inres) >= 1 and orders[i] in inres:
			continue
		if len(inres) < t:
			inres.append(orders[i])
			tablescleaned += 1
			continue
		tablescleaned += 1
		temp = set(inres)
		for j in range(i + 1, no):
			if len(temp) == 1:
				break
			if orders[j] in temp:
				temp.remove(orders[j])
		inres.remove(list(temp)[0])
		inres.append(orders[i])
	print(tablescleaned)


t = int(input())
for z in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	o = []
	c = 0
	for i in range(m):
		if len(o) >= 1 and l[i] in o:
			continue
		c += 1
		if len(o) < n:
			o.append(l[i])
			continue
		temp = set(o)
		for j in range(i + 1, m):
			if len(temp) == 1:
				break
			if l[j] in temp:
				temp.remove(l[j])
		o.remove(list(temp)[0])
		o.append(l[i])
	print(c)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	tmp = []
	count = 0
	for i in range(len(lst)):
		if lst[i] not in tmp:
			if n > 0:
				tmp.append(lst[i])
				lst[i] = -1
				count += 1
				n -= 1
				continue
			farthest = 0
			ind = 0
			for j in range(len(tmp)):
				if tmp[j] not in lst:
					tmp[j] = lst[i]
					count += 1
					break
				val = lst.index(tmp[j])
				if val > farthest:
					farthest = val
					ind = j
			else:
				tmp[ind] = lst[i]
				count += 1
		lst[i] = -1
	print(count)


res = []

def cleantable(test):
	for test_case in range(test):
		(n, m) = map(int, input().split())
		count = 0
		allot = []
		cust = list(map(int, input().split()))
		for i in range(len(cust)):
			if cust[i] in allot:
				pass
			elif n != 0:
				allot.append(cust[i])
				count += 1
				n -= 1
			else:
				temp = cust[i:]
				last = -1
				replace = 0
				for (idx, j) in enumerate(allot):
					if j in temp:
						temp1 = temp.index(j)
						if temp1 > last:
							last = temp1
							replace = idx
					else:
						replace = idx
						break
				allot[replace] = cust[i]
				count += 1
		res.append(count)
t = int(input())
cleantable(t)
for r in res:
	print(r)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	marray = list(map(int, input().split()))
	ans = 0
	occupied = 0
	occupied_array = []
	for ma in range(m):
		if marray[ma] in occupied_array:
			pass
		elif occupied < n:
			occupied += 1
			occupied_array.append(marray[ma])
			ans += 1
		else:
			temp = marray[ma:]
			last = -1
			replace = 0
			for (idx, j) in enumerate(occupied_array):
				if j in temp:
					temp1 = temp.index(j)
					if temp1 > last:
						last = temp1
						replace = idx
				else:
					replace = idx
					break
			occupied_array[replace] = marray[ma]
			ans += 1
	print(ans)


import collections

def isExistingInTable(tables, item):
	flag = False
	for each in tables:
		if each == item:
			flag = True
	return flag

def isEmptyTable(tables):
	flag = False
	cnt = 0
	for each in tables:
		if each == -1:
			cnt = cnt + 1
	if cnt == 0:
		return False
	else:
		return True

def rep_and_adj(rem_list, to_fit, ans):
	if len(rem_list) == 0:
		for each in tables:
			if each != to_fit:
				pos = tables.index(each)
				tables[pos] = to_fit
				ans = ans + 1
				return ans
	else:
		flag = False
		for each in tables:
			if each != -1 and each not in rem_list:
				pos = tables.index(each)
				tables[pos] = to_fit
				ans = ans + 1
				flag = True
				break
		if flag == False:
			rem_list2 = []
			for e in rem_list:
				if e in tables:
					rem_list2.append(e)
			if rem_list2 != None and len(rem_list2) > 0:
				dist = []
				to_replace = -1
				for each in rem_list2:
					if each not in dist and len(dist) == len(tables) - 1:
						to_replace = each
						break
					elif each not in dist:
						dist.append(each)
			for (n, z) in enumerate(tables):
				if z == to_replace:
					tables[n] = to_fit
					ans = ans + 1
					break
		return ans
t = int(input().strip())
while t > 0:
	(n, m) = map(int, input().strip().split())
	nums = list(map(int, input().strip().split()))
	tables = [-1] * n
	ans = 0
	i = 0
	while i < len(nums):
		to_fit = nums[i]
		if isExistingInTable(tables, to_fit) == True:
			pass
		elif isEmptyTable(tables) == True:
			for (n, z) in enumerate(tables):
				if z == -1:
					tables[n] = to_fit
					ans = ans + 1
					break
		else:
			rem_list = nums[i + 1:]
			ans = rep_and_adj(rem_list, to_fit, ans)
		i = i + 1
	print(ans)
	t = t - 1


for t in range(int(input())):
	(n, m) = map(int, input().split())
	c = list(map(int, input().split()))
	table = set()
	count = 0
	for i in range(m):
		customer = c[i]
		if customer in table:
			continue
		count += 1
		if len(table) < n:
			table.add(customer)
			continue
		temp = table.copy()
		for j in range(i + 1, m):
			if len(temp) == 1:
				break
			if c[j] in temp:
				temp.remove(c[j])
		a = temp.pop()
		table.remove(a)
		table.add(customer)
	print(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	order = list(map(int, input().split()))
	already = set()
	count = 0
	for i in range(m):
		x = order[i]
		if x in already:
			continue
		count += 1
		if len(already) < n:
			already.add(x)
			continue
		temp = set(list(already))
		for j in range(i + 1, m):
			if len(temp) == 1:
				break
			if order[j] in temp:
				temp.remove(order[j])
		a = list(temp)[0]
		already.remove(a)
		already.add(x)
	print(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	tables = [0] * n
	clean = 0
	for i in range(m):
		cust = arr[i]
		if cust in tables:
			continue
		elif 0 in tables:
			ind = tables.index(0)
			tables[ind] = cust
			clean += 1
			continue
		left = arr[i + 1:]
		flag = 0
		dist = [0] * n
		for j in range(n):
			if tables[j] not in left:
				tables[j] = cust
				clean += 1
				flag = 1
				break
			dist[j] = left.index(tables[j])
		if flag == 0:
			maxVal = max(dist)
			repInd = dist.index(maxVal)
			tables[repInd] = cust
			clean += 1
	print(clean)


tc = int(input())
for i in range(tc):
	(n, m) = list(map(int, input().split()))
	list1 = list(map(int, input().split()))
	list2 = [x for x in list1]
	set1 = set(list1)
	if n >= len(set1):
		print(len(set1))
	else:
		list3 = []
		count = 0
		for (i, each) in enumerate(list1):
			if each in list3:
				continue
			elif len(list3) < n:
				count += 1
				list3.append(each)
			elif len(list3) == n:
				temp_ind_dict = {}
				for (j, cus) in enumerate(list3):
					try:
						ind = list1[i + 1:].index(cus)
						temp_ind_dict[ind] = j
					except:
						ind = -1
						temp_ind_dict[ind] = j
						break
				if -1 in temp_ind_dict.keys():
					pop_ind = -1
				else:
					pop_ind = max(temp_ind_dict.keys())
				list3.pop(temp_ind_dict[pop_ind])
				list3.append(each)
				count += 1
		print(count)


t = int(input())
for _t in range(t):
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().strip().split()]
	(W, tbl) = (dict(), set())
	for (idx, el) in enumerate(a):
		W[el] = [idx] + W.get(el, [])
	count = 0
	for (idx, el) in enumerate(a):
		if el in tbl:
			W[el].pop()
		elif len(tbl) < n:
			tbl.add(el)
			W[el].pop()
			count += 1
		else:
			(tmp, tmp_c) = (0, -1)
			for c in tbl:
				if len(W[c]) > 0 and W[c][-1] - idx > tmp:
					tmp = W[c][-1] - idx
					tmp_c = c
				elif len(W[c]) == 0:
					tmp = 10 ** 9
					tmp_c = c
					break
			tbl.remove(tmp_c)
			tbl.add(el)
			W[el].pop()
			count += 1
	print(count)


t = int(input())
while t:
	n_m = [int(i) for i in input().split()]
	customers = [int(i) for i in input().split()]
	n = n_m[0]
	m = n_m[1]
	tables = dict()
	washing = 0
	for i in range(len(customers)):
		if len(tables) < n:
			if not customers[i] in tables.keys():
				tables[customers[i]] = customers[i]
				washing += 1
		elif not customers[i] in tables.keys():
			max_key = list(tables.keys())[0]
			res = {}
			aa = set()
			for k in tables.keys():
				res[k] = 9999
			for j in range(i + 1, len(customers)):
				if customers[j] not in aa and customers[j] in tables.keys():
					res[customers[j]] = j
					aa.add(customers[j])
			max_key = max(res, key=res.get)
			del tables[max_key]
			tables[customers[i]] = customers[i]
			washing += 1
	print(washing)
	t -= 1


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	C = list(map(int, input().split()))
	arr = [[100000 for i in range(M)] for j in range(402)]
	for i in range(len(C) - 1, -1, -1):
		pos = i
		arr[C[i]][i] = pos
		for j in range(i - 1, -1, -1):
			if C[j] == C[i]:
				pos = j
			arr[C[i]][j] = pos
	tab = [-1] * N
	count = 0
	for i in range(len(C)):
		if C[i] in tab:
			continue
		else:
			for j in range(len(tab)):
				if tab[j] == -1:
					tab[j] = C[i]
					count += 1
					break
			else:
				trr = [arr[j][i] for j in tab]
				minn = trr.index(max(trr))
				tab[minn] = C[i]
				count += 1
	print(count)


import sys
import math
from collections import defaultdict
import bisect
import heapq

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

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

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 1000000000 + 7
for _ in range(int(input())):
	(N, M) = ilele()
	A = alele()
	c = 0
	clean = 0
	OnTable = []
	for i in range(len(A)):
		if c < N:
			if A[i] not in OnTable:
				c += 1
				clean += 1
				OnTable.append(A[i])
		else:
			maxi = -1
			ele = None
			if A[i] not in OnTable:
				h = 0
				for j in OnTable:
					if j not in A[i:]:
						h = 1
						OnTable.remove(j)
						clean += 1
						OnTable.append(A[i])
						break
					else:
						x = A[i:].index(j)
						if x > maxi:
							maxi = x
							ele = j
				if h == 0:
					OnTable.remove(ele)
					clean += 1
					OnTable.append(A[i])
	print(clean)


from sys import stdin

def minimum(arr, M, N):
	tables = [0] * N
	j = 0
	clean = 0
	for i in range(M):
		if arr[i] in tables:
			continue
		if j < N:
			tables[j] = arr[i]
			clean += 1
			j += 1
		else:
			k = i + 1
			liste = tables.copy()
			while k < M:
				if arr[k] in liste:
					last = arr[k]
					liste.remove(arr[k])
				k += 1
				if len(liste) <= 0:
					break
			if len(liste) <= 0:
				index = tables.index(last)
			else:
				index = tables.index(liste[0])
			tables[index] = arr[i]
			clean += 1
	return clean

def main():
	T = int(stdin.readline())
	for test in range(T):
		(N, M) = [int(x) for x in stdin.readline().split()]
		array = [int(x) for x in stdin.readline().split()]
		print(minimum(array, M, N))
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = list(map(int, input().split()))
	tables = []
	count = 0
	for i in range(m):
		if c[i] in tables:
			continue
		count += 1
		if len(tables) < n:
			tables.append(c[i])
			continue
		x = 0
		temp = tables.copy()
		for x in c[i + 1:]:
			if len(temp) <= 1:
				break
			if x in temp:
				temp.remove(x)
		tables.append(c[i])
		tables.remove(temp[0])
	print(count)


T = int(input())
for z in range(T):
	(N, M) = map(int, input().split())
	lst = list(map(int, input().split()))
	occupied = []
	clean = 0
	for i in range(M):
		elem = lst[i]
		if elem in occupied:
			continue
		clean += 1
		if len(occupied) < N:
			occupied.append(elem)
			continue
		tmp_occ = occupied[:]
		tmp_m = lst[i + 1:]
		for x in tmp_m:
			if len(tmp_occ) <= 1:
				break
			if x in tmp_occ:
				tmp_occ.remove(x)
		occupied.append(elem)
		occupied.remove(tmp_occ[0])
	print(clean)


for _ in range(int(input())):
	(tables, orders) = map(int, input().split())
	actual_orders = [int(x) for x in input().split()]
	occupied = []
	cleans = 0
	for i in range(orders):
		if actual_orders[i] in occupied:
			continue
		cleans += 1
		if len(occupied) < tables:
			occupied.append(actual_orders[i])
			continue
		tmp = set(occupied)
		for j in range(i + 1, orders):
			if len(tmp) == 1:
				break
			if actual_orders[j] in tmp:
				tmp.remove(actual_orders[j])
		occupied.remove(list(tmp)[0])
		occupied.append(actual_orders[i])
	print(cleans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	o = list(map(int, input().split()))
	l = []
	cleans = 0
	for i in range(m):
		if o[i] in l:
			continue
		cleans += 1
		if len(l) < n:
			l.append(o[i])
			continue
		tmp = set(l)
		for j in range(i + 1, m):
			if len(tmp) == 1:
				break
			if o[j] in tmp:
				tmp.remove(o[j])
		l.remove(list(tmp)[0])
		l.append(o[i])
	print(cleans)


from collections import defaultdict
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = list(map(int, input().split()))
	co = defaultdict(int)
	ro = defaultdict(int)
	for i in c:
		ro[i] += 1
	t = 0
	ans = 0
	for (j, i) in enumerate(c):
		if not co[i] and t < n:
			co[i] = 1
			ro[i] -= 1
			ans += 1
			t += 1
		elif not co[i]:
			for k in ro:
				if ro[k] == 0 and co[k]:
					co[k] = 0
					ro[i] -= 1
					co[i] = 1
					ans += 1
					break
			else:
				f = defaultdict(int)
				fd = None
				for k in c[j + 1:]:
					if not f[k] and co[k]:
						f[k] = 1
						fd = k
				co[fd] = 0
				co[i] = 1
				ro[i] -= 1
				ans += 1
		else:
			ro[i] -= 1
	print(ans)


for _ in range(int(input())):
	(num_tables, num_orders) = map(int, input().split())
	orders = list(map(int, input().split()))
	prev_occurance = {}
	next_occurance = [float('inf')] * num_orders
	for i in range(num_orders - 1, -1, -1):
		if orders[i] in prev_occurance:
			next_occurance[i] = prev_occurance[orders[i]]
		prev_occurance[orders[i]] = i
	sitting = {}
	cleaning_count = 0
	for i in range(num_orders):
		if orders[i] not in sitting:
			if len(sitting) == num_tables:
				remove_customer = -1
				customer_next_occrance = -1
				for customer in sitting:
					if sitting[customer] > customer_next_occrance:
						customer_next_occrance = sitting[customer]
						remove_customer = customer
				del sitting[remove_customer]
			cleaning_count += 1
		sitting[orders[i]] = next_occurance[i]
	print(cleaning_count)


t = int(input())
for i in range(t):
	(N, M) = map(int, input().split())
	C = [int(i) for i in input().split()]
	h = set()
	count = 0
	for (idx, elem) in enumerate(C):
		if elem in h:
			continue
		if len(h) < N:
			h.add(elem)
			count += 1
		else:
			farthest = -1
			check = True
			for e in h:
				try:
					farthest = max(C.index(e, idx + 1), farthest)
					check = True
				except:
					check = False
					h.remove(e)
					h.add(elem)
					count += 1
					break
			if check:
				h.remove(C[farthest])
				h.add(elem)
				count += 1
	print(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	array = list(map(int, input().split()))
	s = set()
	count = 0
	for i in range(m):
		if array[i] in s:
			continue
		elif len(s) < n:
			s.add(array[i])
			count += 1
		else:
			farthest = -1
			check = True
			for v in s:
				try:
					farthest = max(array[i + 1:].index(v) + i + 1, farthest)
				except:
					check = False
					s.discard(v)
					s.add(array[i])
					count += 1
					break
			if check:
				s.remove(array[farthest])
				s.add(array[i])
				count += 1
	print(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	array = list(map(int, input().split()))
	s = set()
	count = 0
	for i in range(m):
		if array[i] in s:
			continue
		elif len(s) < n:
			s.add(array[i])
			count += 1
		else:
			ele = -1
			for v in s:
				if v not in array[i + 1:]:
					ele = v
					break
			if ele != -1:
				s.discard(ele)
				s.add(array[i])
				count += 1
			else:
				farthest = -1
				for v in s:
					ind = array[i + 1:].index(v) + i + 1
					farthest = max(farthest, ind)
				s.discard(array[farthest])
				s.add(array[i])
				count += 1
	print(count)


MAX = 401
for T in range(int(input())):
	(N, M) = map(int, input().split())
	C = list(map(int, input().split()))
	orders = [0] * MAX
	seated = [False] * MAX
	for c in C:
		orders[c] += 1
	clean = 0
	for i in range(M):
		c = C[i]
		if not seated[c] and N > 0:
			clean += 1
			seated[c] = True
			N -= 1
		elif not seated[c] and N == 0:
			swap = -1
			temp = list(seated)
			for j in range(i + 1, M):
				cj = C[j]
				if temp[cj]:
					swap = cj
					temp[cj] = False
			for j in range(MAX):
				if seated[j] and orders[j] == 0:
					swap = j
					break
			clean += 1
			seated[swap] = False
			seated[c] = True
		orders[c] -= 1
	print(clean)


T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	o = list(map(int, input().split()))
	cnt = 0
	for i in range(m):
		o[i] -= 1
	ls = [-1 for i in range(n)]
	if len(set(o)) < n:
		print(len(set(o)))
	else:
		k = 0
		for i in range(n):
			if o[i] not in ls:
				ls[k] = o[i]
				k += 1
				cnt += 1
		for j in range(n, m):
			if o[j] not in ls:
				if ls.count(-1) != 0:
					ls[ls.index(-1)] = o[j]
					cnt += 1
				else:
					max = -2
					flag = 0
					for p in ls:
						if o[j + 1:].count(p) == 0:
							ls[ls.index(p)] = o[j]
							cnt += 1
							flag = 1
							break
						elif o[j + 1:].index(p) > max:
							max = o[j + 1:].index(p)
					if flag == 0:
						ls[ls.index(o[j + 1 + max])] = o[j]
						cnt += 1
		print(cnt)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	order = list(map(int, input().split()))
	already = set()
	count = 0
	for i in range(m):
		if order[i] not in already and len(already) < n:
			already.add(order[i])
			count += 1
		elif order[i] not in already and len(already) == n:
			flag = True
			temp = []
			for each in already:
				try:
					temp.append(i + 1 + order[i + 1:].index(each))
				except:
					flag = False
					already.remove(each)
					already.add(order[i])
					count += 1
					break
			if flag:
				bestindex = max(temp)
				already.remove(order[bestindex])
				already.add(order[i])
				count += 1
	print(count)


t = int(input())
from collections import defaultdict as dd
for ijk in range(0, t):
	freq = dd(list)
	(n, m) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	for i in range(0, m):
		freq[a[i]].append(i)
	occ = [0] * n
	ans = 0
	for i in range(0, m):
		if a[i] in occ:
			freq[a[i]] = freq[a[i]][1:]
			continue
		else:
			tmp = -1
			index = -1
			freq[a[i]] = freq[a[i]][1:]
			flag = False
			for j in range(0, n):
				if occ[j] == 0:
					occ[j] = a[i]
					ans += 1
					flag = True
					break
				if freq[occ[j]] == []:
					index = j
					break
				elif freq[occ[j]][0] > tmp:
					index = j
					tmp = freq[occ[j]][0]
			if flag == False:
				occ[index] = a[i]
				ans += 1
	print(ans)


t = int(input())
for i in range(t):
	z = 0
	(n, m) = [int(x) for x in input().split()]
	order = [int(x) for x in input().split()]
	table = set()
	for i in range(m):
		x = order[i]
		if x in table:
			continue
		z += 1
		if len(table) < n:
			table.add(x)
			continue
		l = set(list(table))
		for j in range(i + 1, m):
			if len(l) == 1:
				break
			if order[j] in l:
				l.remove(order[j])
		a = list(l)[0]
		table.remove(a)
		table.add(x)
	print(z)


t = int(input())
for i in range(t):
	z = 0
	(n, m) = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	cur = set()
	for i in range(m):
		x = c[i]
		if x in cur:
			continue
		z += 1
		if len(cur) < n:
			cur.add(x)
			continue
		left = set(list(cur))
		for j in range(i + 1, m):
			if len(left) == 1:
				break
			if c[j] in left:
				left.remove(c[j])
		torem = list(left)[0]
		cur.remove(torem)
		cur.add(x)
	print(z)


a = int(input())
for i in range(a):
	(t, r) = map(int, input().split())
	di = {}
	dp = {}
	dn = {}
	count = 0
	l = list(map(int, input().split()))
	for i in l:
		if i in di:
			di[i] += 1
			dn[i] += 1
		else:
			di[i] = 1
			dn[i] = 1
	i = 0
	while i < len(l):
		if l[i] in dp:
			dp[l[i]].append(i)
		else:
			dp[l[i]] = []
			dp[l[i]].append(i)
		i += 1
	cache = [(-7, -7)] * t
	allocc = []
	for i in l:
		if i not in allocc:
			if (-7, -7) in cache:
				h = 0
				k = cache.index((-7, -7))
				dn[i] -= 1
				if dn[i] > 0:
					m = di[i] - dn[i]
					h = dp[i][m]
				else:
					h = 500
				cache[k] = (h, i)
				allocc.append(i)
			else:
				h = 0
				j = cache.index(max(cache))
				dn[i] -= 1
				if dn[i] > 0:
					m = di[i] - dn[i]
					h = dp[i][m]
				else:
					h = 500
				del allocc[allocc.index(cache[j][1])]
				cache[j] = (h, i)
				allocc.append(cache[j][1])
			count += 1
		else:
			m = di[i] - dn[i]
			k = cache.index((dp[i][m], i))
			dn[i] -= 1
			if dn[i] > 0:
				m = di[i] - dn[i]
				cache[k] = (dp[i][m], i)
			else:
				cache[k] = (500, i)
			pass
	print(count)


printswitch = False

def pr(*args):
	if printswitch:
		for i in args:
			print(i, ' ', end='')
		print('')
t = int(input())
res = []
for i in range(t):
	count = 0
	(noOfTables, noOfOrders) = map(int, input().split())
	orders = list(map(int, input().split()))
	dicc = {}
	for index in range(len(orders)):
		if orders[index] not in dicc:
			dicc[orders[index]] = [index]
		else:
			dicc[orders[index]].append(index)
	tableOccupancy = {}
	for ind in range(len(orders)):
		pr('tc=', i, ' order=', orders[ind], ' ind:', ind, 'tableOccupancy: ', tableOccupancy, 'noOftables:', noOfTables)
		if noOfTables > 0:
			if orders[ind] in tableOccupancy:
				pr('debug 1')
				dicc[orders[ind]].remove(ind)
			else:
				pr('debug 2')
				dicc[orders[ind]].remove(ind)
				tableOccupancy[orders[ind]] = dicc[orders[ind]]
				count += 1
				noOfTables -= 1
		elif orders[ind] in tableOccupancy:
			pr('debug 3')
			dicc[orders[ind]].remove(ind)
			tableOccupancy[orders[ind]] = dicc[orders[ind]]
		else:
			pr('debug 4-------------------------------------------------------------')
			nulllistfound = False
			for (k, v) in tableOccupancy.items():
				if len(v) == 0:
					tableOccupancy.pop(k)
					dicc[orders[ind]].remove(ind)
					tableOccupancy[orders[ind]] = dicc[orders[ind]]
					count += 1
					nulllistfound = True
					break
			if nulllistfound:
				pr('debug 5')
				continue
			else:
				pr('debug 6')
				ordertoremove = max(tableOccupancy, key=lambda k: tableOccupancy[k][0])
				tableOccupancy.pop(ordertoremove)
				dicc[orders[ind]].remove(ind)
				tableOccupancy[orders[ind]] = dicc[orders[ind]]
				count += 1
	res.append(count)
for k in res:
	print(k)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	ls = list(map(int, input().split()))
	m = [0] * 401
	lastSeen = [0] * 401
	present = [False] * 401
	for i in range(M):
		m[ls[i]] = i
	Count = table = 0
	for i in range(M):
		if present[ls[i]]:
			continue
		if table < N:
			present[ls[i]] = True
			table += 1
		else:
			r = -1
			for j in range(i - 1, -1, -1):
				if present[ls[j]] and m[ls[j]] == j:
					r = ls[j]
					break
			if r == -1:
				for j in range(i + 1, M):
					if present[ls[j]] and lastSeen[ls[j]] != i:
						r = ls[j]
						lastSeen[ls[j]] = i
			present[r] = False
			present[ls[i]] = True
		Count += 1
	print(Count)


t = int(input())
for ii in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	s = set(a)
	d = {}
	ans = 0
	for i in range(k):
		d[a[i]] = []
	for i in range(k):
		d[a[i]].append(i)
	se = set()
	arr = []
	c = 0
	for i in range(k):
		if a[i] in se:
			d[a[i]].pop(0)
			continue
		if a[i] not in se:
			if c < n:
				arr.append(a[i])
				se.add(a[i])
				d[a[i]].pop(0)
				c += 1
				ans += 1
			else:
				kk = []
				kt = 0
				for j in arr:
					if d[j] == []:
						kt = 1
						nu = j
						break
					else:
						kk.append((d[j][0], j))
				if kt == 0:
					kk = max(kk)
					kk = kk[1]
					arr.remove(kk)
					se.remove(kk)
					se.add(a[i])
					arr.append(a[i])
					d[a[i]].pop(0)
					ans += 1
				else:
					arr.remove(nu)
					arr.append(a[i])
					se.remove(nu)
					se.add(a[i])
					d[a[i]].pop(0)
					ans += 1
	print(ans)


def replaceTable(orders, tables, x, n):
	occ = [-1] * n
	for i in range(n):
		if tables[i] in orders[x + 1:]:
			occ[i] = orders[x + 1:].index(tables[i])
	if -1 in occ:
		return occ.index(-1)
	else:
		return occ.index(max(occ))
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	orders = [a[0]]
	for i in range(1, m):
		if a[i] != a[i - 1]:
			orders.append(a[i])
	m = len(orders)
	tables = []
	count = 0
	for i in range(m):
		if orders[i] in tables:
			continue
		if len(tables) < n:
			tables.append(orders[i])
		else:
			j = replaceTable(orders, tables, i, n)
			tables[j] = orders[i]
		count += 1
	print(count)


def find_table(tables, orders):
	maxOrderIndex = 0
	tableIndex = 0
	for (it, t) in enumerate(tables):
		if t not in orders:
			return it
		if orders.index(t) > maxOrderIndex:
			maxOrderIndex = orders.index(t)
			tableIndex = it
	return tableIndex
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	orders = [int(x) for x in input().split()]
	tables = [0 for x in range(n)]
	counter = 0
	for (idx, order) in enumerate(orders):
		if order in tables:
			continue
		elif 0 in tables:
			index0 = tables.index(0)
			tables[index0] = order
			counter += 1
		else:
			tab = find_table(tables, orders[idx:])
			tables[tab] = order
			counter += 1
	print(counter)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l2 = []
	d1 = {}
	d2 = {}
	for i in l:
		d1[i] = False
		d2[i] = d2.get(i, 0) + 1
	c = 0
	for i in range(m):
		if not d1[l[i]]:
			if len(l2) != n:
				l2.append(l[i])
				d1[l[i]] = True
				d2[l[i]] -= 1
				c += 1
			else:
				mi = -1
				ma = -1
				for j in range(n):
					if d2[l2[j]] == 0:
						mi = j
						break
					else:
						for k in range(i + 1, m):
							if l2[j] == l[k]:
								if k > ma:
									ma = k
									mi = j
								break
				d1[l2.pop(mi)] = False
				c += 1
				l2.append(l[i])
				d1[l[i]] = True
				d2[l[i]] -= 1
		else:
			d2[l[i]] -= 1
	print(c)


for _ in range(int(input().strip())):
	(n, m) = map(int, input().strip().split())
	requests = list(map(int, input().strip().split()))
	remaining_reqs = dict()
	for req in requests:
		remaining_reqs[req] = remaining_reqs.get(req, 0) + 1
	occupied_tables = 0
	seated = dict()
	for req in set(requests):
		seated[req] = False
	clean_count = 0
	current_idx = 0
	for req in requests:
		if seated[req]:
			remaining_reqs[req] -= 1
		elif occupied_tables < n:
			clean_count += 1
			seated[req] = True
			remaining_reqs[req] -= 1
			occupied_tables += 1
		else:
			max_recent_idx = -1
			idx = None
			for rem_req in remaining_reqs:
				if seated[rem_req]:
					try:
						rem_req_idx = requests[current_idx + 1:].index(rem_req)
					except ValueError:
						idx = rem_req
						break
					if rem_req_idx > max_recent_idx:
						max_recent_idx = rem_req_idx
						idx = rem_req
			seated[idx] = False
			clean_count += 1
			seated[req] = True
			remaining_reqs[req] -= 1
		current_idx += 1
	print(clean_count)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	tables = []
	ans = 0
	for (k, i) in enumerate(arr):
		if len(tables) < n and i not in tables:
			tables.append(i)
			ans += 1
		elif i in tables:
			continue
		else:
			support = []
			flag = True
			for j in tables:
				if j not in arr[k:]:
					support.append(-1)
					tables.remove(j)
					tables.append(i)
					ans += 1
					flag = False
					break
				else:
					support.append(arr[k:].index(j))
			if flag:
				tables.remove(arr[k:][max(support)])
				tables.append(i)
				ans += 1
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	orders = list(map(int, input().split()))
	tables = set()
	present = 0
	ans = 0
	for i in range(m):
		if orders[i] not in tables:
			ans += 1
			if present < n:
				tables.add(orders[i])
				present += 1
			else:
				last = orders[i - 1]
				temp_dict = {}
				j = i + 1
				while len(temp_dict) < present and j < m:
					if orders[j] in tables:
						if orders[j] not in temp_dict:
							last = orders[j]
							temp_dict[last] = last
					j += 1
				if len(temp_dict) < present:
					for element in tables:
						if element not in temp_dict:
							last = element
							break
				tables.remove(last)
				tables.add(orders[i])
	print(ans)


def compute_person_tracker(meal_orders):
	personTracker = {}
	for i in range(len(meal_orders)):
		if meal_orders[i] in personTracker:
			personTracker[meal_orders[i]].append(i)
		else:
			personTracker[meal_orders[i]] = [i]
	return personTracker

def find_the_farest(table_tracker, personTracker):
	farest = -1
	far_index = -1
	for i in range(len(table_tracker)):
		if not personTracker[table_tracker[i]]:
			return i
		elif personTracker[table_tracker[i]][0] >= farest:
			farest = personTracker[table_tracker[i]][0]
			far_index = i
	return far_index

def number_of_cleans(tables, no_orders, meal_orders):
	person_tracker = compute_person_tracker(meal_orders)
	table_tracker = [-1] * tables
	cleans = 0
	track = 0
	for order in meal_orders:
		if order not in table_tracker:
			cleans = cleans + 1
			if table_tracker[tables - 1] == -1:
				table_tracker[track] = order
				person_tracker[order] = person_tracker[order][1:]
				track += 1
			else:
				table_tracker[find_the_farest(table_tracker, person_tracker)] = order
				person_tracker[order] = person_tracker[order][1:]
		else:
			person_tracker[order] = person_tracker[order][1:]
	print(cleans)
T = int(input())
for i in range(T):
	(tables, no_orders) = [int(x) for x in input().split()]
	meal_orders = [int(x) for x in input().split()]
	number_of_cleans(tables, no_orders, meal_orders)


from sys import stdin
t = int(input())
for k in range(t):
	count = 0
	d = {}
	(n, m) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	for i in range(len(l)):
		if str(l[i]) not in d.keys():
			d[str(l[i])] = 1
		else:
			d[str(l[i])] += 1
	if n < len(set(l)):
		temp_li = []
		for i in range(len(l)):
			if l[i] not in temp_li and len(temp_li) < n:
				temp_li.append(l[i])
				count += 1
			elif l[i] not in temp_li:
				local = -1000000000
				temp = local
				val = 0
				for m in range(len(temp_li)):
					if temp_li[m] in l[i + 1:]:
						temp1 = l[i + 1:].index(temp_li[m])
						local = max(local, temp1)
						if temp < local:
							temp = local
							val = m
					else:
						val = m
						break
				temp_li[val] = l[i]
				count += 1
		print(count)
	else:
		print(str(len(set(l))))