Chef is given two strings A and B of length N containing lowercase English letters.

Chef can rearrange both the strings in any way he wants. He wants to minimize the length of LCS ([Longest Common Subsequence] of both the strings.

Find the minimum length of LCS of A and B if he optimally rearranges both the strings.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N - denoting the length of A and B.
- The second line of each test case contains a string A.
- The third line of each test case contains a string B.

------ Output Format ------ 

For each test case, output the minimum length of LCS Chef can obtain.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$A$ and $B$ contain lowercase English letters
- The sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
4
aaaa
aaab
1
c
z
5
abcde
cdefg

----- Sample Output 1 ------ 
3
0
1

----- explanation 1 ------ 
Test case 1: $\mathrm{LCS}(\texttt{aaaa}, \texttt{aaab}) = \texttt{aaa}$. It can be shown that no other rearrangement of the strings produces a smaller LCS.

Test case 3: $\mathrm{LCS}(\texttt{acbed}, \texttt{gdefc}) = \texttt{c}$. Note that multiple longest common subsequences exist for this arrangement. It can be shown that no other rearrangement of the strings produces a smaller LCS.

Source: codechef | Difficulty: EASY
Tags: Greedy algorithms


Solutions:
for _ in range(int(input())):
	input()
	ai = [i for i in input()]
	bi = [i for i in input()]
	count = 0
	for i in set(ai):
		if i in bi:
			x = min(ai.count(i), bi.count(i))
			if x > count:
				count = x
	print(count)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	(a, b) = (input(), input())
	(da, db) = (dict(Counter(a)), dict(Counter(b)))
	d = dict()
	for (x, y) in da.items():
		d[x] = min(y, db.get(x, 0))
	for (x, y) in db.items():
		d[x] = min(y, da.get(x, 0))
	print(max(d.values()))


import collections
tt = int(input())
for i in range(tt):
	n = int(input())
	a = input()
	b = input()
	x = collections.Counter(a)
	y = collections.Counter(b)
	mx = 0
	for i in x.keys():
		if i in y.keys():
			res = min(x[i], y[i])
			mx = max(res, mx)
	print(mx)


from collections import Counter
for t in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	c = Counter(a)
	d = Counter(b)
	x = {}
	for i in c:
		x[i] = min(c[i], d[i])
	y = max(x.values())
	print(y)


t = int(input())
for T in range(t):
	n = int(input())
	a = input()
	b = input()

	def solve(a, b):
		a1 = [0] * 26
		b1 = [0] * 26
		for i in a:
			a1[ord(i) - 97] += 1
		for i in b:
			b1[ord(i) - 97] += 1
		ans = 0
		for i in range(26):
			ans = max(min(a1[i], b1[i]), ans)
		return ans
	a = solve(a, b)
	print(a)


for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	(x, y) = (set(a), set(b))
	ans = 0
	for i in x:
		if i in y:
			ans = max(ans, min(a.count(i), b.count(i)))
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	c = 0
	t = 0
	d = set(list(a))
	for j in d:
		if j in b:
			if a.count(j) > b.count(j):
				t = b.count(j)
			else:
				t = a.count(j)
		if t > c:
			c = t
	print(c)


for i in range(int(input())):
	n = int(input())
	s = input()
	s1 = input()
	(a, b) = (set(s), set(s1))
	l = []
	for i in a:
		if i in b:
			l.append(min(s.count(i), s1.count(i)))
	if l != []:
		print(max(l))
	else:
		print(0)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	a = Counter(a)
	b = Counter(b)
	e = {}
	for i in a:
		e[i] = min(a[i], b.get(i, 0))
	print(max(e.values()))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	a = Counter(s1)
	b = Counter(s2)
	res = 0
	for k in a:
		if k in b:
			res = max(res, min(a[k], b[k]))
	print(res)


import collections as cnt
for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	c = cnt.Counter(a)
	d = cnt.Counter(b)
	e = {}
	for i in c:
		e[i] = min(c[i], d.get(i, 0))
	print(max(e.values()))


for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	s = set(a)
	c = 0
	for i in s:
		if i in b:
			x = a.count(i)
			y = b.count(i)
			m = min(x, y)
			if m > c:
				c = m
	print(c)


for _ in range(int(input())):
	n = int(input())
	l1 = input()
	l2 = input()
	dp1 = [0] * 26
	dp2 = [0] * 26
	ans = 0
	for x in range(n):
		dp1[ord(l1[x]) - 97] += 1
		dp2[ord(l2[x]) - 97] += 1
	for x in range(26):
		if dp1[x] > 0 and dp2[x] > 0:
			mini = min(dp1[x], dp2[x])
			ans = max(ans, mini)
	print(ans)


import sys

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

def fast_out(n):
	sys.stdout.write(str(n) + '\n')
T = int(input())
for n1 in range(T):
	n = int(input())
	a = input()
	b = input()
	z = 0
	for i in [chr(i) for i in range(ord('a'), ord('z') + 1)]:
		z = max(z, min(a.count(i), b.count(i)))
	print(z)


for _ in range(int(input())):
	n = int(input())
	A = input()
	B = input()
	l = []
	c = 0
	sa = set(list(A))
	for i in sa:
		if i in B:
			a = A.count(i)
			b = B.count(i)
			m = min(a, b)
			if m > c:
				c = m
	print(c)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = input()
	b = input()
	A = [0] * 26
	B = [0] * 26
	for (x, y) in zip(a, b):
		A[ord(x) - ord('a')] += 1
		B[ord(y) - ord('a')] += 1
	ans = 0
	for i in range(26):
		if A[i] > 0 and B[i] > 0:
			if A[i] > B[i]:
				ans = max(B[i], ans)
			else:
				ans = max(A[i], ans)
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	la = list(a)
	lb = list(b)
	ta = set(la)
	c = k = 0
	for i in ta:
		if i in lb:
			if a.count(i) > b.count(i):
				c = b.count(i)
			else:
				c = a.count(i)
		if c > k:
			k = c
	print(k)


from collections import Counter, defaultdict
import sys

def sol(n, A, B):
	c1 = Counter(A)
	c2 = Counter(B)
	ans = 0
	del c1['\n']
	del c2['\n']
	for x in c1:
		if x in c2:
			ans = max(ans, min(c1[x], c2[x]))
	if ans == float('inf'):
		return 0
	return ans
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return str(input())

def invr():
	return map(int, input().split())
T = inp()
for i in range(T):
	n = inp()
	a = insr()
	b = insr()
	print(sol(n, a, b))


for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	l = []
	from collections import Counter
	a = Counter(a)
	b = Counter(b)
	for (x, y) in a.items():
		if x in b:
			z = b.get(x)
			z1 = a.get(x)
			mini = min(z, z1)
			l.append(mini)
	if len(l) == 0:
		print(0)
	else:
		print(max(l))


n = int(input())
for _ in range(0, n):
	l = int(input())
	m = l
	a = input()
	b = input()
	d = {}
	n = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in b:
		if i in n:
			n[i] += 1
		else:
			n[i] = 1
	ans = 0
	for i in d:
		if i in n:
			ans = max(ans, min(d[i], n[i]))
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	arr = [0] * 26
	arr1 = [0] * 26
	for k in range(len(a)):
		p = ord(a[k]) - 97
		arr[p] = arr[p] + 1
	for k in range(len(b)):
		p = ord(b[k]) - 97
		arr1[p] = arr1[p] + 1
	m = 0
	for n in range(26):
		if arr[n] != 0 and arr1[n] != 0:
			if arr[n] > arr1[n]:
				s = arr1[n]
			else:
				s = arr[n]
			if s > m:
				m = s
	print(m)


t = int(input())
for j in range(t):
	n = int(input())
	a = input()
	b = input()
	ar1 = [0] * 26
	ar2 = [0] * 26
	for i in range(len(a)):
		ar1[ord(a[i]) - ord('a')] += 1
	for i in range(len(b)):
		ar2[ord(b[i]) - ord('a')] += 1
	res = 0
	for i in range(26):
		res = max(res, min(ar1[i], ar2[i]))
	print(res)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = input()
	b = input()
	l1 = [0] * 26
	l2 = [0] * 26
	count = 0
	for i in a:
		l1[ord(i) - 97] += 1
	for i in b:
		l2[ord(i) - 97] += 1
	for i in range(0, len(l1)):
		count = max(count, min(l1[i], l2[i]))
	print(count)


def di(k, arr):
	arr = [0] * 26
	for i in k:
		arr[ord(i) - ord('a')] += 1
	return arr
t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	arr1 = [0] * 26
	arr2 = [0] * 26
	a1 = di(a, arr1)
	b1 = di(b, arr2)
	ans = 0
	for i in range(26):
		ans = max(ans, min(a1[i], b1[i]))
	print(ans)


t = int(input())
for i in range(t):
	l = int(input())
	s1 = input()
	s2 = input()
	d1 = {}
	d2 = {}
	for i in s1:
		if i in d1:
			d1[i] += 1
		else:
			d1[i] = 1
	for i in s2:
		if i in d2:
			d2[i] += 1
		else:
			d2[i] = 1
	ans = 0
	for i in range(26):
		if chr(i + 97) in d1 and chr(i + 97) in d2:
			ans = max(ans, min(d1[chr(i + 97)], d2[chr(i + 97)]))
	print(ans)


T = int(input())
for i in range(T):
	N = int(input())
	A = input()
	B = input()
	l1 = [0] * 26
	l2 = [0] * 26
	for j in A:
		l1[ord(j) - 97] = l1[ord(j) - 97] + 1
	for j in B:
		l2[ord(j) - 97] = l2[ord(j) - 97] + 1
	m = 0
	for j in range(len(l1)):
		if l1[j] != 0 and l2[j] != 0:
			if l1[j] < l2[j]:
				s = l1[j]
			else:
				s = l2[j]
			if s > m:
				m = s
	print(m)


import math
T = int(input())
for _ in range(T):
	N = int(input())
	A = input()
	B = input()
	X = [0] * 26
	Y = [0] * 26
	ans = 0
	for i in A:
		X[ord(i) - 97] += 1
	for i in B:
		Y[ord(i) - 97] += 1
	for i in range(0, 26):
		ans = max(ans, min(X[i], Y[i]))
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	arr1 = [0] * 26
	arr2 = [0] * 26
	for i in range(n):
		arr1[ord(a[i]) - ord('a')] += 1
	for i in range(n):
		arr2[ord(b[i]) - ord('a')] += 1
	res = 0
	for i in range(26):
		res = max(res, min(arr1[i], arr2[i]))
	print(res)


t = int(input())
for _ in range(t):
	N = int(input())
	A = input()
	B = input()
	ans = []
	d1 = {}
	d2 = {}
	for i in A:
		d1[i] = d1.get(i, 0) + 1
	for j in B:
		d2[j] = d2.get(j, 0) + 1
	for k in d1.keys():
		if k not in d2.keys():
			pass
		else:
			ans.append(min(d1[k], d2[k]))
	if len(ans) == 0:
		print(0)
	else:
		print(max(ans))


from collections import Counter
for t in range(int(input())):
	n = int(input())
	a1 = input()
	a2 = input()
	a = [0] * 26
	b = [0] * 26
	for i in a1:
		a[ord(i) - 97] += 1
	for i in a2:
		b[ord(i) - 97] += 1
	l = []
	for i in range(26):
		if a[i] != 0 and b[i] != 0:
			l.append(min(a[i], b[i]))
	if not l:
		print(0)
	else:
		print(max(l))


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	d1 = {}
	d2 = {}
	for j in a:
		if j in d1:
			d1[j] += 1
		else:
			d1[j] = 1
	for j in b:
		if j in d2:
			d2[j] += 1
		else:
			d2[j] = 1
	m = 0
	for j in d1.keys():
		if j in d2.keys():
			m = max(m, min(d1[j], d2[j]))
	print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	l1 = [0] * 26
	l2 = [0] * 26
	for i in a:
		l1[ord(i) - 97] += 1
	for j in b:
		l2[ord(j) - 97] += 1
	ans = 0
	for i in range(26):
		ans = max(min(l1[i], l2[i]), ans)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	A = input()
	B = input()
	freq1 = [0] * 26
	freq2 = [0] * 26
	for char1 in A:
		freq1[ord(char1) - 97] += 1
	for char2 in B:
		freq2[ord(char2) - 97] += 1
	ans = 0
	for i in range(26):
		ans = max(ans, min(freq1[i], freq2[i]))
	print(ans)


T = int(input())
for i in range(T):
	N = int(input())
	A = input()
	B = input()
	Arr = [0] * 26
	Brr = [0] * 26
	for i in range(N):
		k = ord(A[i]) - ord('a')
		Arr[k] += 1
	for i in range(N):
		m = ord(B[i]) - ord('a')
		Brr[m] += 1
	ans = 0
	for i in range(26):
		ans = max(ans, min(Arr[i], Brr[i]))
	print(ans)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	d1 = Counter(a)
	d2 = Counter(b)
	s = set(a)
	l = []
	for i in s:
		l.append(min(d1[i], d2[i]))
	print(max(l))


def solution(text1, text2, n):
	arr = [0] * 26
	brr = [0] * 26
	for i in text1:
		arr[ord(i) - ord('a')] += 1
	for j in text2:
		brr[ord(j) - ord('a')] += 1
	ans = 0
	for i in range(26):
		ans = max(ans, min(arr[i], brr[i]))
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	st1 = input()
	st2 = input()
	print(solution(st1, st2, n))


for i in range(int(input())):
	N = int(input())
	A = input()
	B = input()
	arr1 = [0] * 26
	arr2 = [0] * 26
	for char in A:
		arr1[ord(char) - ord('a')] += 1
	for char in B:
		arr2[ord(char) - ord('a')] += 1
	ans = 0
	for i in range(26):
		ans = max(ans, min(arr1[i], arr2[i]))
	print(ans)


def solve(a, b):
	d1 = dict()
	b = list(b)
	for i in a:
		if i in d1:
			if i in b:
				d1[i] += 1
				b.remove(i)
		elif i in b:
			d1[i] = 1
			b.remove(i)
	lst = list(d1.values())
	lst.append(0)
	ans = max(lst)
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	print(solve(a, b))


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	c = [0] * 26
	d = [0] * 26
	for i in a:
		c[ord(i) - 97] += 1
	for i in b:
		d[ord(i) - 97] += 1
	ans = 0
	for i in range(26):
		m = min(c[i], d[i])
		ans = max(m, ans)
	print(ans)


T = int(input())
for i in range(T):
	N = int(input())
	A = input()
	B = input()
	d1 = dict()
	d2 = dict()
	for i in A:
		if i in d1:
			d1[i] = d1[i] + 1
		else:
			d1[i] = 1
	for i in B:
		if i in d2:
			d2[i] = d2[i] + 1
		else:
			d2[i] = 1
	ans = 0
	for i in d1:
		if i in d2:
			ans = max(ans, min(d1[i], d2[i]))
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	l1 = [0] * 26
	l2 = [0] * 26
	for i in s1:
		l1[ord(i) - 97] += 1
	for i in s2:
		l2[ord(i) - 97] += 1
	ans = 0
	for i in range(26):
		ans = max(ans, min(l1[i], l2[i]))
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	a1 = [0] * 26
	a2 = [0] * 26
	for i in a:
		a1[ord(i) - 97] += 1
	for i in b:
		a2[ord(i) - 97] += 1
	m = 0
	for i in range(26):
		ma = min(a1[i], a2[i])
		m = max(m, ma)
	print(m)


for _ in range(int(input())):
	x = int(input())
	s1 = input()[:x]
	s2 = input()[:x]
	a = [0] * 26
	b = [0] * 26
	for i in s1:
		a[ord(i) % 97] += 1
	for i in s2:
		b[ord(i) % 97] += 1
	m = 0
	for i in range(26):
		m = max(m, min(a[i], b[i]))
	print(m)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	arr = [0] * 26
	arrb = [0] * 26
	ans = 0
	for i in range(len(a)):
		arr[ord(a[i]) - ord('a')] += 1
	for i in range(len(b)):
		arrb[ord(b[i]) - ord('a')] += 1
	for i in range(len(arr)):
		ans = max(ans, min(arr[i], arrb[i]))
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	arr1 = [0] * 26
	arr2 = [0] * 26
	for i in range(n):
		arr1[ord(a[i]) - 97] += 1
	for i in range(n):
		arr2[ord(b[i]) - 97] += 1
	ans = 0
	for i in range(26):
		ans = max(ans, min(arr1[i], arr2[i]))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	arr = [0] * 26
	brr = [0] * 26
	for i in a:
		arr[ord(i) - 97] += 1
	for i in b:
		brr[ord(i) - 97] += 1
	m = 0
	for i in range(26):
		mi = min(arr[i], brr[i])
		m = max(m, mi)
	print(m)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	d1 = Counter(a)
	d2 = Counter(b)
	s = 0
	for i in d1.keys():
		if i in d2.keys():
			m = min(d1[i], d2[i])
			s = max(m, s)
	print(s)


t = int(input())
t1 = 0
while t1 < t:
	n = int(input())
	s1 = input()
	s2 = input()
	a1 = []
	a2 = []
	for i in range(0, 26):
		a1.append(0)
		a2.append(0)
	for i in range(0, n):
		a1[ord(s1[i]) - 97] = a1[ord(s1[i]) - 97] + 1
		a2[ord(s2[i]) - 97] = a2[ord(s2[i]) - 97] + 1
	l = []
	for i in range(0, 26):
		l.append(min(a1[i], a2[i]))
	m = max(l)
	print(m)
	t1 = t1 + 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	hashA = [0] * 26
	hashB = [0] * 26
	for i in a:
		hashA[ord(i) - 97] += 1
	for i in b:
		hashB[ord(i) - 97] += 1
	for i in range(26):
		hashA[i] = min(hashA[i], hashB[i])
	print(max(hashA))


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

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

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def lcs(s1, s2, m, n, dp):
	if dp[m][n] != -1:
		return dp[m][n]
	if m == 0 or n == 0:
		dp[m][n] = 0
		return 0
	if s1[m - 1] == s2[n - 1]:
		dp[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, dp)
		return dp[m][n]
	dp[m - 1][n] = lcs(s1, s2, m - 1, n, dp)
	dp[m][n - 1] = lcs(s1, s2, m, n - 1, dp)
	return max(lcs(s1, s2, m - 1, n, dp), lcs(s1, s2, m, n - 1, dp))
t = inp()
for i in range(t):
	n = inp()
	s1 = st()
	s2 = st()
	l = [0] * 26
	l1 = [0] * 26
	m = 0
	for i in range(n):
		l[ord(s1[i]) - 97] += 1
		l1[ord(s2[i]) - 97] += 1
	for i in range(26):
		m = max(m, min(l[i], l1[i]))
	print(m)


from collections import Counter
for t in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	da = dict(Counter(a))
	db = dict(Counter(b))
	samefreq = []
	for i in range(97, 123):
		if da.get(chr(i)) and db.get(chr(i)):
			samefreq.append(min(da[chr(i)], db[chr(i)]))
	if not samefreq:
		print(0)
	else:
		print(max(samefreq))


t = int(input())
for _ in range(t):
	l = int(input())
	a = input()
	b = input()
	aarr = [0] * 26
	barr = [0] * 26
	for i in a:
		aarr[ord(i) - 97] += 1
	for i in b:
		barr[ord(i) - 97] += 1
	m = 0
	for i in range(26):
		m = max(m, min(aarr[i], barr[i]))
	print(m)


for i in range(int(input())):
	n = int(input())
	s1 = list(input())
	s2 = list(input())
	from collections import Counter
	d1 = Counter(s1)
	d2 = Counter(s2)
	ans = 0
	for i in s1:
		if i in d1 and i in d2:
			x = min(d1[i], d2[i])
			ans = max(ans, x)
	print(ans)


import sys
import math
from collections import defaultdict, Counter
from itertools import permutations
from collections import deque
from decimal import Decimal
from fractions import Fraction
from heapq import heappush, heappop
import bisect

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

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

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

def multiple():
	return [int(x) for x in sys.stdin.readline().split()]

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

def sqrt(x):
	(low, high) = (0, x)
	while low <= high:
		mid = (low + high) // 2
		if mid * mid <= x < (mid + 1) * (mid + 1):
			return mid
		elif x < mid * mid:
			high = mid - 1
		else:
			low = mid + 1
t = sin()
for _ in range(t):
	n = sin()
	s = string()
	t = string()
	res1 = Counter(s)
	res2 = Counter(t)
	ans = 0
	for (k, v) in res1.items():
		if k in res2:
			ans = max(ans, min(v, res2[k]))
	print(ans)


from collections import Counter

class T:

	def solve(self):
		n = int(input())
		a = sorted(input())
		b = sorted(input())
		c = 0
		d = dict()
		if n == 1:
			return 1 if a == b else 0
		da = Counter(a)
		db = Counter(b)
		ans = 0
		for i in da:
			if i in db:
				ans = max(ans, min(da[i], db[i]))
		return ans
for t in range(int(input())):
	obj = T()
	print(obj.solve())


for _ in range(int(input())):
	n = int(input())
	A = input()
	B = input()
	s = set(A + B)
	l = []
	for i in s:
		a1 = A.count(i)
		b1 = B.count(i)
		l.append(min(a1, b1))
	print(max(l))


for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	s = set(a + b)
	l = []
	for i in s:
		a1 = a.count(i)
		b1 = b.count(i)
		l.append(min(a1, b1))
	print(max(l))


n = int(input())
for ii in range(n):
	l = int(input())
	s1 = input()
	s2 = input()
	ans = 0
	a = {}
	b = {}
	for k in range(l):
		a[s1[k]] = 0
		b[s2[k]] = 0
	for k in range(l):
		a[s1[k]] += 1
		b[s2[k]] += 1
	for kk in a:
		try:
			ans = max(ans, min(a[kk], b[kk]))
		except:
			pass
	print(ans)


for i in range(int(input())):
	a = int(input())
	s = input()
	s1 = input()
	l = []
	s2 = set(s + s1)
	for i in s2:
		b = s.count(i)
		c = s1.count(i)
		l.append(min(b, c))
	print(max(l))


for t in range(int(input())):
	a = int(input())
	st_1 = input()
	st_2 = input()
	S = set(st_1 + st_2)
	l = []
	for i in S:
		m = st_1.count(i)
		n = st_2.count(i)
		l.append(min(m, n))
	else:
		print(max(l))


for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	la = list(a)
	lb = list(b)
	sa = set(list(a))
	t = 0
	c = 0
	for i in sa:
		if i in lb:
			if a.count(i) > b.count(i):
				t = b.count(i)
			else:
				t = a.count(i)
		if t > c:
			c = t
	print(c)


import collections
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	(x, y) = (collections.Counter(a), collections.Counter(b))
	ans = 0
	alp = 'qwertyuiopasdfghjklzxcvbnm'
	for c in alp:
		if c not in x or c not in y:
			continue
		ans = max(ans, min(x[c], y[c]))
	print(ans)


import collections
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	(d1, d2) = (collections.Counter(a), collections.Counter(b))
	ans = 0
	alf = 'qwertyuiopasdfghjklzxcvbnm'
	for c in alf:
		if c not in d1 or c not in d2:
			continue
		ans = max(ans, min(d1[c], d2[c]))
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	b = list(input())
	ans = 0
	x = [0] * 26
	y = [0] * 26
	z = [0] * 26
	for i in range(n):
		x[ord(s[i]) - 97] += 1
		y[ord(b[i]) - 97] += 1
	for i in range(26):
		z[i] = min(x[i], y[i])
	print(max(z))


t = int(input())
while t:
	n = int(input())
	a = input()
	b = input()
	d1 = {}
	d2 = {}
	for i in a:
		if i in d1.keys():
			d1[i] += 1
		else:
			d1[i] = 1
	for i in b:
		if i in d2.keys():
			d2[i] += 1
		else:
			d2[i] = 1
	alp = 'abcdefghijklmnopqrstuvwxyz'
	mini = 0
	for i in alp:
		if i not in d1 or i not in d2:
			continue
		mini = max(mini, min(d1[i], d2[i]))
	print(mini)
	t -= 1