A cafe has N computers. Several customers come to the cafe to use these computers. A customer will be serviced only if there is any unoccupied computer at the moment the customer visits the cafe. If there is no unoccupied computer, the customer leaves the cafe. 
You are given an integer N representing the number of computers in the cafe and a sequence of uppercase letters S. Every letter in S occurs exactly two times. The first occurrence denotes the arrival of a customer and the second occurrence denotes the departure of the same customer if he gets allocated the computer. 
You have to find the number of customers that walked away without using a computer.
Example 1:
Input:
N = 3
S = GACCBDDBAGEE
Output: 1
Explanation: Only D will not be able to 
get any computer. So the answer is 1.
Example 2:
N = 1
S = ABCBAC
Output: 2
Explanation: B and C will not be able to 
get any computers. So the answer is 2.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function solve() which takes the integer N (the number of computers in the cafe) and the string S (denoting the arrival and departure of a customer) as input parameters and returns an integer representing the number of customers that walked away without using a computer.
 
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 26
1 <= |S| <= 52
S consists of uppercase English letters and each letter occurs exactly 2 times.

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3



class Solution:

    def solve(self, n, s):

        ans = 0

        # Write your code here

        

        return ans

Solutions:
class Solution:

	def solve(self, n, s):
		ans = 0
		l = [0] * 26
		k = n
		res = 0
		for i in s:
			p = ord(i) - 65
			if l[p] == 1:
				k += 1
				l[p] = 0
			elif l[p] == 0:
				if k == 0:
					ans += 1
					l[p] = -1
				else:
					k -= 1
					l[p] = 1
		return ans


class Solution:

	def solve(self, n, s):
		ans = 0
		curr = 0
		d = {}
		ret = {}
		for i in s:
			if d.get(i):
				curr -= 1
				del d[i]
			elif ret.get(i):
				continue
			elif curr == n:
				ans += 1
				ret[i] = 1
			else:
				d[i] = 1
				curr += 1
		return ans


class Solution:

	def solve(self, n, s):
		ans = 0
		freq = [0] * 26
		count = 0
		for cur in s:
			value = ord(cur) - 65
			if freq[value] == 0:
				freq[value] = 1
				if count < n:
					freq[value] = 2
					count += 1
				else:
					ans += 1
			else:
				if freq[value] == 2:
					count -= 1
				freq[value] = 0
		return ans


class Solution:

	def solve(self, n, s):
		visited = []
		got = []
		count = 0
		ans = 0
		for i in range(len(s)):
			if s[i] not in visited:
				if count < n:
					count += 1
					got.append(s[i])
				else:
					ans += 1
				visited.append(s[i])
			else:
				if s[i] in got:
					count -= 1
					got.remove(s[i])
				visited.remove(s[i])
		return ans


class Solution:

	def solve(self, n, s):
		ans = 0
		dec = {}
		count = 0
		for i in s:
			status = dec.get(i)
			if status == 1:
				count -= 1
			elif status == None:
				if count == n:
					dec[i] = 0
					ans += 1
				else:
					dec[i] = 1
					count += 1
		return ans
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	ob = Solution()
	ans = ob.solve(n, s)
	print(ans)


class Solution:

	def solve(self, n, s):
		ans = 0
		occ = set()
		leave = set()
		for i in s:
			if i not in occ:
				if i in leave:
					continue
				if n > 0:
					n = n - 1
					occ.add(i)
				else:
					ans += 1
					leave.add(i)
			else:
				occ.remove(i)
				n += 1
		return ans
		return ans


class Solution:

	def solve(self, n, S):
		ans = 0
		s = set()
		walked = set()
		for ch in S:
			if ch in s:
				s.remove(ch)
			else:
				if ch in walked:
					continue
				if len(s) == n:
					walked.add(ch)
					ans += 1
				else:
					s.add(ch)
		return ans