*"You have a reason to leave this place, but I don't."*

In the fourth game, Sang-Woo and Ali are competing against each other. Sang-Woo is the more intelligent one between them, and he plans to win the game by cheating. Ali is your childhood friend and you want to help him win this game. The game goes as follows.

Both of them are given 2 strings — S and P — of equal length (say N). The task is to find the minimum number of operations required to convert the string P into S. Every character of both S and P is either a lowercase English alphabet or ?.

First, before performing any operation, you must choose a single lowercase character from the English alphabet, and replace every occurrence of ? with this character. Note that every ? present in either S or P is replaced by the exact same character. This does not count as an operation.

Once the above step is done, you are allowed to perform the following two operations on P any number of times:
Pick an index 1 ≤ i ≤ N such that P_{i} is a vowel, and change P_{i} to any consonant.
Pick an index 1 ≤ i ≤ N such that P_{i} is a consonant, and change P_{i} to any vowel.

Note: The vowels are the 5 characters \{a, e, i, o, u\} — the other 21 are consonants.

Find the minimum number of operations required to convert P into S.

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N, denoting the length of strings S and P.
- The second and third lines contain strings S and P respectively.

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

For each test case, output in a single line the minimum number of operations required to convert P into S.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
- The sum of all $N$ across all test cases does not exceed $5*10^{5}$.
$|S| = |P|$
- Every character of both $S$ and $P$ is either a lowercase English alphabet or $?$.
- Every $?$ present in $S$ and $P$ should be assigned the same character.

----- Sample Input 1 ------ 
3
5
ab?c?
aeg?k
6
abcde?
ehio??
4
abcd
abcd
----- Sample Output 1 ------ 
4
6
0
----- explanation 1 ------ 
Test Case 1: First, replace every $?$ by $u$. This gives us $S = abucu$ and $P = aeguk$. Now $P$ can be converted to $S$ as follows:
1. Convert $P_{2} = e$ to $b$ in 1 operation.
2. Convert $P_{3} = g$ to $u$ in 1 operation.
3. Convert $P_{4} = u$ to $c$ in 1 operation.
4. Convert $P_{5} = k$ to $u$ in 1 operation.

Test Case 3: The strings are already equal, so no operations are required.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

String algorithms

Complete search

Data structures

Ad-hoc


Solutions:
for tc in range(int(input())):
	n = int(input())
	s = input()
	p = input()
	s1 = 0
	v = {'a', 'e', 'i', 'o', 'u'}
	dv = {}
	dc = {}
	for i in range(n):
		if s[i] != p[i]:
			if s[i] != '?' and p[i] != '?':
				if s[i] in v and p[i] not in v:
					s1 += 1
				elif s[i] not in v and p[i] in v:
					s1 += 1
				else:
					s1 += 2
			else:
				if s[i] == '?':
					c = p[i]
				else:
					c = s[i]
				if c in v:
					if c in dv:
						dv[c] += 1
					else:
						dv[c] = 1
				elif c in dc:
					dc[c] += 1
				else:
					dc[c] = 1
	(dc, dv) = (list(dc.values()), list(dv.values()))
	(dc_sum, dv_sum) = (sum(dc), sum(dv))
	(dc_max, dv_max) = (max(dc, default=0), max(dv, default=0))
	print(s1 + min(2 * (dc_sum - dc_max) + dv_sum, 2 * (dv_sum - dv_max) + dc_sum))


from collections import Counter

def calc(s, p):
	res = 0
	for i in range(len(p)):
		a = s[i]
		b = p[i]
		if a == b:
			continue
		if a in 'aeiou' and b not in 'aeiuo':
			res += 1
		elif a not in 'aeiou' and b in 'aeiuo':
			res += 1
		else:
			res += 2
	return res
for t in range(int(input())):
	n = int(input())
	p = input()
	s = input()
	s1 = []
	p1 = []
	s2 = []
	p2 = []
	vowels = Counter()
	cons = Counter()
	for i in range(len(p)):
		if p[i] == '?' and s[i] != '?':
			if s[i] in 'aeiuo':
				vowels[s[i]] += 1
			else:
				cons[s[i]] += 1
		elif p[i] != '?' and s[i] == '?':
			if p[i] in 'aeiuo':
				vowels[p[i]] += 1
			else:
				cons[p[i]] += 1
	vowel = 'a'
	con = 'b'
	for (key, val) in vowels.items():
		if val > vowels[vowel]:
			vowel = key
	for (key, val) in cons.items():
		if val > cons[con]:
			con = key
	for i in range(len(p)):
		if s[i] == '?':
			s1.append(vowel)
			s2.append(con)
		else:
			s1.append(s[i])
			s2.append(s[i])
		if p[i] == '?':
			p1.append(vowel)
			p2.append(con)
		else:
			p1.append(p[i])
			p2.append(p[i])
	print(min(calc(s1, p1), calc(s2, p2)))


from collections import defaultdict
v = 'aeiou'
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	p = str(input())
	d = defaultdict(lambda : 0)
	dd = defaultdict(lambda : 0)
	ans = 0
	m1 = 0
	m2 = 0
	c1 = 0
	c2 = 0
	for (i, j) in zip(s, p):
		if i == j:
			if i == '?':
				f = 1
			continue
		if i != '?' and j != '?':
			x = int(i in v) + int(j in v)
			if x == 1:
				ans += 1
			else:
				ans += 2
			continue
		elif i == '?':
			if j not in v:
				c2 += 1
				dd[j] += 1
				m2 = max(m2, dd[j])
			else:
				c1 += 1
				d[j] += 1
				m1 = max(m1, d[j])
		elif j == '?':
			if i not in v:
				c2 += 1
				dd[i] += 1
				m2 = max(m2, dd[i])
			else:
				c1 += 1
				d[i] += 1
				m1 = max(m1, d[i])
	ans += min(2 * (c1 - m1) + c2, 2 * (c2 - m2) + c1)
	print(ans)


vowels = {'a', 'e', 'i', 'o', 'u'}

def changeops(a, b):
	if a == b:
		return 0
	elif a in vowels and b in vowels:
		return 2
	elif a not in vowels and b not in vowels:
		return 2
	else:
		return 1
t = int(input())
for _ in range(t):
	n = int(input())
	change = [0 for i in range(n)]
	vowcount = {}
	conscount = {}
	for i in range(97, 123):
		if chr(i) in vowels:
			vowcount[chr(i)] = 0
		else:
			conscount[chr(i)] = 0
	s = str(input())
	p = str(input())
	for j in range(n):
		si = s[j]
		pi = p[j]
		if si != '?' and pi != '?':
			change[j] = changeops(si, pi)
		if si == '?' and pi == '?':
			change[j] = 0
		elif si == '?':
			if pi in vowels:
				vowcount[pi] += 1
			else:
				conscount[pi] += 1
		elif pi == '?':
			if si in vowels:
				vowcount[si] += 1
			else:
				conscount[si] += 1
	totvow = sum(vowcount.values())
	totcons = sum(conscount.values())
	opcount = []
	for v in vowcount:
		opcount.append(totcons + (totvow - vowcount[v]) * 2)
	for c in conscount:
		opcount.append(totvow + (totcons - conscount[c]) * 2)
	print(min(opcount) + sum(change))


for _ in range(int(input())):
	n = int(input())
	s = input()
	p = input()
	res = 0
	v = 0
	dv = {}
	mv = 0
	c = 0
	dc = {}
	mc = 0
	for i in range(n):
		a = s[i]
		b = p[i]
		if a == b:
			continue
		if a == '?' or b == '?':
			if a == '?':
				l = b
			else:
				l = a
			if l in ['a', 'e', 'i', 'o', 'u']:
				v += 1
				dv[l] = dv.get(l, 0) + 1
				mv = max(dv[l], mv)
			else:
				c += 1
				dc[l] = dc.get(l, 0) + 1
				mc = max(dc[l], mc)
			continue
		av = False
		bv = False
		if a in ['a', 'e', 'i', 'o', 'u']:
			av = True
		if b in ['a', 'e', 'i', 'o', 'u']:
			bv = True
		if av == bv:
			res += 2
		else:
			res += 1
	c_cost = (c - mc) * 2 + v
	v_cost = (v - mv) * 2 + c
	print(res + min(c_cost, v_cost))


def check_vowel(x):
	if x in 'aeiou':
		return True
	return False

def get_min_move(s, p, N):
	min_move = N * 2
	for ch in 'abcdefghijklmnopqrstuvwxyz':
		s_arr = s
		p_arr = p
		s_arr = s_arr.replace('?', ch)
		p_arr = p_arr.replace('?', ch)
		move = 0
		for i in range(N):
			s_arr_vowel = check_vowel(s_arr[i])
			p_arr_vowel = check_vowel(p_arr[i])
			if s_arr[i] == p_arr[i]:
				continue
			elif s_arr_vowel and (not p_arr_vowel):
				move += 1
			elif p_arr_vowel and (not s_arr_vowel):
				move += 1
			else:
				move += 2
		if move < min_move:
			min_move = move
	return min_move
for i in range(int(input())):
	N = int(input())
	s_arr = input()
	p_arr = input()
	min_move = get_min_move(s_arr, p_arr, N)
	print(min_move)


def check_vowel(x):
	if x == 'a' or x == 'e' or x == 'i' or (x == 'o') or (x == 'u'):
		return True
	return False

def get_min_move(s, p, N):
	min_move = 99999999999999
	for ch in 'abcdefghijklmnopqrstuvwxyz':
		s_arr = s
		p_arr = p
		s_arr = s_arr.replace('?', ch)
		p_arr = p_arr.replace('?', ch)
		move = 0
		for i in range(N):
			if s_arr[i] == p_arr[i]:
				pass
			elif s_arr[i] in 'aeiou' and p_arr[i] not in 'aeiou':
				move += 1
			elif p_arr[i] in 'aeiou' and s_arr[i] not in 'aeiou':
				move += 1
			else:
				move += 2
		if move == 0:
			min_move = move
			break
		else:
			min_move = min(move, min_move)
	return min_move
for i in range(int(input())):
	N = int(input())
	s_arr = input()
	p_arr = input()
	min_move = get_min_move(s_arr, p_arr, N)
	print(min_move)


import string
V = ['a', 'e', 'i', 'o', 'u']
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	p = list(input())
	d = dict.fromkeys(string.ascii_lowercase, 0)
	ans = 0
	vc = 0
	cc = 0
	for i in range(n):
		if s[i] != p[i]:
			if s[i] == '?':
				d[p[i]] += 1
				if p[i] in V:
					vc += 1
				else:
					cc += 1
			elif p[i] == '?':
				d[s[i]] += 1
				if s[i] in V:
					vc += 1
				else:
					cc += 1
			elif s[i] in V and p[i] in V:
				ans += 2
			elif s[i] in V and p[i] not in V:
				ans += 1
			elif s[i] not in V and p[i] in V:
				ans += 1
			elif s[i] not in V and p[i] not in V:
				ans += 2
	(vm, cm) = [0, 0]
	for i in list(d.keys()):
		if i in V:
			vm = max(vm, d[i])
		else:
			cm = max(cm, d[i])
	ans = ans + min((cc - cm) * 2 + vc, (vc - vm) * 2 + cc, cc * 2 + vc, vc * 2 + cc)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	ans = 0
	cons = ['b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 'y', 'z']
	vowel = ['a', 'e', 'i', 'o', 'u']
	(dc, dv) = ({}, {})
	i = 0
	while i < n:
		if a[i] != b[i]:
			if a[i] in cons and b[i] in vowel or (a[i] in vowel and b[i] in cons):
				ans += 1
			elif a[i] in cons and b[i] in cons or (a[i] in vowel and b[i] in vowel):
				ans += 2
			elif a[i] == '?':
				if b[i] in cons:
					temp = dc.get(b[i], 0) + 1
					dc[b[i]] = temp
				else:
					temp = dv.get(b[i], 0) + 1
					dv[b[i]] = temp
			elif b[i] == '?':
				if a[i] in cons:
					temp = dc.get(a[i], 0) + 1
					dc[a[i]] = temp
				else:
					temp = dv.get(a[i], 0) + 1
					dv[a[i]] = temp
		i += 1
	x = 2 * (sum(dv.values()) - max(dv.values(), default=0)) + sum(dc.values())
	y = 2 * (sum(dc.values()) - max(dc.values(), default=0)) + sum(dv.values())
	print(ans + min(x, y))


inp = lambda : int(input())
mul = lambda : map(int, input().split())
jn = lambda x, l: x.join(map(str, l))
slst = lambda : list(input().split()[0])
silst = lambda : list(map(int, input().split()[0]))
lst = lambda : list(map(int, input().split()))
dd = lambda : defaultdict(lambda : 0)
import sys
input = sys.stdin.readline
from collections import defaultdict
from math import ceil, log, floor, sqrt, gcd, log10

def merge(a, lo, hi, m):
	tmp = []
	i = lo
	j = m + 1
	while i <= m and j <= hi:
		if a[i] > a[j]:
			tmp += [a[j]]
			j += 1
		else:
			tmp += [a[i]]
			i += 1
	while i <= m:
		tmp += [a[i]]
		i += 1
	while j <= hi:
		tmp += [a[j]]
		j += 1
	j = 0
	for i in range(lo, hi + 1):
		a[i] = tmp[j]
		j += 1

def msrt(arr, lo, hi):
	if lo < hi:
		m = (lo + hi) // 2
		msrt(arr, lo, m)
		msrt(arr, m + 1, hi)
		merge(arr, lo, hi, m)
for _ in range(inp()):
	n = inp()
	s1 = input()
	p1 = input()
	ans = []
	for x in list('abcdefghiklmnopqrstuvwxyz'):
		s = s1
		p = p1
		count = 0
		s = s.replace('?', x)
		p = p.replace('?', x)
		for i in range(n):
			if s[i] == p[i]:
				pass
			elif s[i] in 'aeiou' and p[i] not in 'aeiou':
				count += 1
			elif p[i] in 'aeiou' and s[i] not in 'aeiou':
				count += 1
			else:
				count += 2
		ans.append(count)
	print(min(ans))


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)) + '\n')
vowels = 'aeiou'

def convert(n, p, s):
	count = 0
	for i in range(n):
		if p[i] != s[i]:
			if p[i] in vowels and s[i] in vowels:
				count += 2
			elif p[i] not in vowels and s[i] not in vowels:
				count += 2
			else:
				count += 1
	return count

def main():
	for _ in tr():
		n = nl()
		s = line()
		p = line()
		count = 2 * n
		for i in range(26):
			rep = chr(ord('a') + i)
			count = min(count, convert(n, p.replace('?', rep), s.replace('?', rep)))
		print(count)
main()


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	p = input()
	vowel = ['a', 'e', 'i', 'o', 'u']
	temp = {}
	for i in range(26):
		temp[chr(i + 97)] = 0
	vc = 0
	cc = 0
	ans = 0
	for i in range(0, n):
		if s[i] != p[i]:
			if s[i] == '?':
				temp[p[i]] += 1
				if p[i] in vowel:
					vc += 1
				else:
					cc += 1
			elif p[i] == '?':
				temp[s[i]] += 1
				if s[i] in vowel:
					vc += 1
				else:
					cc += 1
			elif s[i] in vowel:
				if p[i] in vowel:
					ans += 2
				else:
					ans += 1
			elif p[i] in vowel:
				ans += 1
			else:
				ans += 2
	ans_temp = 1000000000
	for i in range(26):
		if chr(i + 97) in vowel:
			ans_temp = min(ans_temp, 2 * (vc - temp[chr(i + 97)]) + cc)
		else:
			ans_temp = min(ans_temp, 2 * (cc - temp[chr(i + 97)]) + vc)
	print(ans + ans_temp)


u = int(input())
vow = {'a', 'e', 'i', 'o', 'u'}
for _ in range(u):
	n = int(input())
	s = input()
	p = input()
	answ = n * 2
	for char in range(ord('a'), ord('z') + 1):
		char = chr(char)
		curr = 0
		for ind in range(n):
			charS = s[ind]
			charP = p[ind]
			if charS == '?':
				charS = char
			if charP == '?':
				charP = char
			if charS == charP:
				continue
			if charS in vow:
				if charP in vow:
					curr += 2
				else:
					curr += 1
			elif charP not in vow:
				curr += 2
			else:
				curr += 1
		if curr < answ:
			answ = curr
	print(answ)


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	l = ['a', 'e', 'i', 'o', 'u']
	(c1, c2, l1, c) = (0, 0, [], 0)
	for i in range(n):
		if s1[i] != s2[i]:
			if s1[i] == '?':
				l1.append(ord(s2[i]))
				if s2[i] in l:
					c1 += 1
				else:
					c2 += 1
			elif s2[i] == '?':
				l1.append(ord(s1[i]))
				if s1[i] in l:
					c1 += 1
				else:
					c2 += 1
			elif s1[i] in l and s2[i] in l or (s1[i] not in l and s2[i] not in l):
				c += 2
			else:
				c += 1
	(k1, k2, k3, k4) = (0, 0, 0, 0)
	if l1 != []:
		l1.sort()
		(d, c3) = ({0: 0}, 1)
		for i in range(len(l1) - 1):
			if l1[i] == l1[i + 1]:
				c3 += 1
			else:
				d[l1[i]] = c3
				c3 = 1
		d[l1[len(l1) - 1]] = c3
		(k1, k2, k3, k4) = (0, 0, 0, 0)
		for i in d:
			if chr(i) in l:
				if d[i] > k2:
					k1 = i
					k2 = d[i]
			elif d[i] > k4:
				k3 = i
				k4 = d[i]
	print(c + min((c1 - d[k1]) * 2 + c2, c1 + (c2 - d[k3]) * 2))


from collections import Counter
import math
for i in range(int(input())):
	n = int(input())
	s = input()
	p = input()
	l = ['a', 'e', 'i', 'o', 'u']
	r = 'qwertyuiopasdfghjklzxcvbnm'
	rr = list(r)
	ss = 0
	sss = math.inf
	for j in rr:
		ss = 0
		ns = s.replace('?', j)
		np = p.replace('?', j)
		for i in range(n):
			if np[i] == ns[i]:
				continue
			elif np[i] in l:
				if ns[i] in l:
					ss += 2
				else:
					ss += 1
			elif ns[i] in l:
				ss += 1
			else:
				ss += 2
		sss = min(sss, ss)
	print(sss)


vowels = ['a', 'e', 'i', 'o', 'u']

def changeOpR(a, b):
	if a == b:
		return 0
	isVowel = [True if a in vowels else False, True if b in vowels else False]
	if isVowel[0] == isVowel[1]:
		return 2
	return 1

def extra(A):
	possibleAns = 1000000
	for i in range(26):
		temp = chr(97 + i)
		sample = A
		countA = 0
		for j in range(len(sample)):
			(x, y) = sample[j]
			if x == '?':
				x = temp
			if y == '?':
				y = temp
			countA += changeOpR(x, y)
		possibleAns = min(possibleAns, countA)
	return possibleAns
for _ in range(int(input())):
	N = int(input())
	S = input()
	P = input()
	count = 0
	A = []
	for i in range(N):
		if S[i] == '?' and P[i] == '?':
			continue
		if S[i] == '?' or P[i] == '?':
			A.append([S[i], P[i]])
		else:
			count += changeOpR(S[i], P[i])
	count += extra(A)
	print(count)


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	s = input()
	p = input()
	ov = 'aeiou'
	c = 0
	v = 0
	d = dict()
	kk = 0
	for i in range(n):
		if s[i] == '?' and p[i] == '?':
			continue
		if s[i] == '?' or p[i] == '?':
			if s[i] != '?':
				if d.get(s[i]):
					d[s[i]] += 1
				else:
					d[s[i]] = 1
				if s[i] in ov:
					v = v + 1
				else:
					c = c + 1
			else:
				if d.get(p[i]):
					d[p[i]] += 1
				else:
					d[p[i]] = 1
				if p[i] in ov:
					v = v + 1
				else:
					c = c + 1
		elif s[i] != p[i]:
			if s[i] in ov and p[i] in ov:
				kk = kk + 2
			elif s[i] in ov and p[i] not in ov:
				kk = kk + 1
			elif s[i] not in ov and p[i] in ov:
				kk = kk + 1
			else:
				kk = kk + 2
	mv = 0
	mc = 0
	for i in d:
		if i in ov:
			if mv < d[i]:
				mv = d[i]
		elif mc < d[i]:
			mc = d[i]
	print(min((v - mv) * 2 + c, (c - mc) * 2 + v) + kk)


vowels = ['a', 'e', 'i', 'o', 'u']
alphabets = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
t = int(input())
while t:
	t = t - 1
	n = int(input())
	S = input()
	P = input()
	source = ''
	target = ''
	count_arr = []
	for x_x in alphabets:
		count = 0
		source = S.replace('?', x_x)
		target = P.replace('?', x_x)
		for i in range(n):
			if source[i] != target[i]:
				if source[i] not in vowels and target[i] not in vowels:
					count = count + 2
				elif source[i] in vowels and target[i] in vowels:
					count = count + 2
				else:
					count = count + 1
		count_arr.append(count)
	print(min(count_arr))


vowel = ['a', 'e', 'i', 'o', 'u']

def check(c):
	return c in vowel
for i in range(int(input())):
	n = int(input())
	s = input()
	p = input()
	ans = 10000000
	for ci in range(26):
		c = chr(ord('a') + ci)
		s2 = s.replace('?', c)
		p2 = p.replace('?', c)
		op = 0
		for (i, j) in zip(s2, p2):
			if i == j:
				continue
			op += 2 if check(i) == check(j) else 1
		ans = min(ans, op)
	print(ans)


from bisect import bisect_left as bl
VOWELS = 'aeiou'
t = int(input())
for _ in range(t):
	n = int(input())
	(s1, s2) = (list(input()), list(input()))
	if s1 == s2:
		print(0)
	else:
		cnt = 2 * n
		for j in range(26):
			ans = 0
			repl = chr(97 + j)
			for i in range(n):
				(v1, v2) = (s1[i] if s1[i] != '?' else repl, s2[i] if s2[i] != '?' else repl)
				if v1 != v2:
					(c1, c2) = (v1 in VOWELS, v2 in VOWELS)
					if c1 and c2 or not (c1 or c2):
						ans += 2
					else:
						ans += 1
			cnt = min(cnt, ans)
		print(cnt)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	p = input()
	vovel = {'a', 'e', 'i', 'o', 'u'}
	ans = 1000000000
	for i in range(26):
		s_d = s.replace('?', chr(97 + i))
		p_d = p.replace('?', chr(97 + i))
		p_ans = 0
		for i in range(n):
			if p_d[i] == s_d[i]:
				pass
			elif p_d[i] in vovel and s_d[i] in vovel or (p_d[i] not in vovel and s_d[i] not in vovel):
				p_ans += 2
			else:
				p_ans += 1
		if ans > p_ans:
			ans = p_ans
	print(ans)


def abc(a, b):
	l1 = []
	x = 'aeiou'
	y = 'bcdfghjklmnpqrstvwxyz'
	for i in range(97, 123):
		count = 0
		s = a.replace('?', chr(i))
		p = b.replace('?', chr(i))
		for j in range(n):
			if s[j] != p[j]:
				if s[j] in x and p[j] in x:
					count += 2
				elif s[j] in x and p[j] in y:
					count += 1
				elif s[j] in y and p[j] in x:
					count += 1
				else:
					count += 2
		l1.append(count)
	return min(l1)
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	print(abc(a, b))


ts = int(input())

def minimum(l, l1):
	score = []
	al = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
	a = l
	b = l1
	vowels = ['a', 'e', 'i', 'o', 'u']
	for j in range(25):
		c = 0
		l = a.replace('?', al[j])
		l1 = b.replace('?', al[j])
		for i in range(len(l)):
			if l[i] != l1[i]:
				c += 1
				if l1[i] not in vowels:
					if l[i] not in vowels:
						c += 1
				elif l1[i] in vowels:
					if l[i] in vowels:
						c += 1
		score.append(c)
	return min(score)
for i in range(ts):
	c = 0
	l = []
	l1 = []
	n = int(input())
	s1 = input()
	s2 = input()
	print(minimum(s1, s2))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	p = input()
	vowel = ('a', 'e', 'i', 'o', 'u')
	d = {}
	ct = 0
	qv = 0
	qc = 0
	streakc = 0
	streakv = 0
	for i in range(n):
		x = p[i]
		z = s[i]
		sf = 10 ** 5
		xv = x in vowel
		zv = z in vowel
		if x == z:
			continue
		if x == '?':
			if z in d:
				d[z] += 1
			else:
				d[z] = 1
			if zv:
				qv += 1
				streakv = max(streakv, d[z])
			else:
				qc += 1
				streakc = max(streakc, d[z])
			continue
		if z == '?':
			if x in d:
				d[x] += 1
			else:
				d[x] = 1
			if xv:
				qv += 1
				streakv = max(streakv, d[x])
			else:
				qc += 1
				streakc = max(streakc, d[x])
			continue
		if xv ^ zv:
			ct += 1
		else:
			ct += 2
	tv = qc + (qv - streakv) * 2
	tc = qv + (qc - streakc) * 2
	ans = min(tv, tc)
	print(ans + ct)


vowels = ['a', 'e', 'i', 'o', 'u']

def changeOpR(a, b):
	if a == b:
		return 0
	isVowel = [True if a in vowels else False, True if b in vowels else False]
	if isVowel[0] == isVowel[1]:
		return 2
	return 1

def extra(A):
	possibleAns = 1000000
	iterate = 'abcdefghijklmnopqrstuvwxyz'
	for i in iterate:
		temp = 0
		for j in A:
			temp += changeOpR(i, j)
		possibleAns = min(possibleAns, temp)
	return possibleAns
for _ in range(int(input())):
	N = int(input())
	S = input()
	P = input()
	count = 0
	A = []
	for i in range(N):
		if S[i] == '?' and P[i] == '?':
			continue
		if S[i] == '?':
			A.append(P[i])
		elif P[i] == '?':
			A.append(S[i])
		else:
			count += changeOpR(S[i], P[i])
	count += extra(A)
	print(count)


import string

def get_count(string1, string2, n, ch):
	string1 = string1.replace('?', ch)
	string2 = string2.replace('?', ch)
	count = 0
	for i in range(n):
		if string1[i] != string2[i]:
			if string1[i] in vowels and string2[i] not in vowels or (string2[i] in vowels and string1[i] not in vowels):
				count += 1
			else:
				count += 2
	return count
t = int(input())
vowels = ['a', 'e', 'i', 'o', 'u']
alphabets = list(string.ascii_lowercase)
for i in range(t):
	min_value = 10000000000000000000000000000000000
	n = int(input())
	string_1 = input()
	string_2 = input()
	for ch in alphabets:
		min_value = min(min_value, get_count(string_1, string_2, n, ch))
	print(min_value)


def fun(a, b, n, car):
	c = 0
	s = set(['a', 'e', 'i', 'o', 'u'])
	f1 = 0
	f2 = 0
	for i in range(n):
		if a[i] == '?':
			a[i] = car
			f1 = 1
		if b[i] == '?':
			b[i] = car
			f2 = 1
		if a[i] != b[i]:
			if a[i] in s and b[i] in s or (a[i] not in s and b[i] not in s):
				c += 2
			else:
				c += 1
		if f1 == 1:
			a[i] = '?'
			f1 = 0
		if f2 == 1:
			b[i] = '?'
			f2 = 0
	return c
import sys
for _ in range(int(input())):
	n = int(sys.stdin.readline())
	a = list(sys.stdin.readline())
	b = list(sys.stdin.readline())
	ans = 2 * n + 1
	for j in range(26):
		ans = min(ans, fun(a, b, n, chr(j + 97)))
	sys.stdout.write(str(ans) + '\n')


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	ans = 10000000007
	o = {'a', 'e', 'i', 'o', 'u'}
	for i in range(26):
		s = a.replace('?', chr(i + 97))
		p = b.replace('?', chr(i + 97))
		r = 0
		for i in range(n):
			if s[i] != p[i]:
				if s[i] not in o and p[i] in o or (s[i] in o and p[i] not in o):
					r += 1
				else:
					r += 2
		ans = min(ans, r)
	print(ans)


def main():
	t = int(input())
	while t > 0:
		n = int(input())
		s = str(input())
		p = str(input())
		ans = n * 2 + 1
		vowels = ['a', 'e', 'i', 'o', 'u']
		for i in range(97, 123):
			Operation = 0
			(temp_s, temp_p) = ('', '')
			temp_s = s.replace('?', chr(i))
			temp_p = p.replace('?', chr(i))
			for j in range(n):
				if temp_s[j] != temp_p[j]:
					if temp_s[j] in vowels and temp_p[j] in vowels:
						Operation += 2
					elif temp_s[j] not in vowels and temp_p[j] not in vowels:
						Operation += 2
					else:
						Operation += 1
			ans = min(ans, Operation)
		print(ans)
		t -= 1
main()


vowel = 'aeiou'
import string
for i in range(int(input())):
	n = int(input())
	(s, p) = (input(), input())
	Min = n * 2
	for j in string.ascii_lowercase:
		x = s
		y = p
		x = x.replace('?', j)
		y = y.replace('?', j)
		ct = 0
		for k in range(n):
			if x[k] != y[k]:
				if x[k] in vowel and y[k] in vowel or (x[k] not in vowel and y[k] not in vowel):
					ct += 2
				else:
					ct += 1
		if ct < Min:
			Min = ct
	print(Min)


import string
letters = string.ascii_lowercase
from sys import stdin, stdout
t = int(stdin.readline())
for i in range(t):
	N = int(stdin.readline())
	S = list(input())
	P = list(input())
	count = 0
	vowels = {'a', 'e', 'i', 'o', 'u'}
	P_new = []
	S_new = []
	for j in range(N):
		if P[j] != S[j] and P[j] != '?' and (S[j] != '?'):
			if P[j] in vowels and S[j] in vowels or (P[j] not in vowels and S[j] not in vowels):
				count += 2
			else:
				count += 1
		if P[j] == '?' or S[j] == '?':
			P_new.append(P[j])
			S_new.append(S[j])
	x = 0
	for k in range(len(S_new)):
		y = True
		if S_new[k] == '?':
			if P_new[k] == S_new[k]:
				y = False
				pass
			elif P_new[k] == 'a':
				pass
			elif P_new[k] in vowels:
				x += 2
			elif P_new[k] not in vowels:
				x += 1
		elif P_new[k] == '?':
			if S_new[k] == P_new[k]:
				pass
			elif S_new[k] == 'a':
				pass
			elif S_new[k] in vowels:
				x += 2
			elif S_new[k] not in vowels:
				x += 1
	for j in letters:
		m = 0
		for k in range(len(S_new)):
			y = True
			if S_new[k] == '?':
				if P_new[k] == S_new[k]:
					y = False
					pass
				elif P_new[k] == j:
					pass
				elif P_new[k] in vowels and j in vowels:
					m += 2
				elif P_new[k] not in vowels and j not in vowels:
					m += 2
				else:
					m += 1
			elif P_new[k] == '?' and y:
				if S_new[k] == P_new[k]:
					pass
				elif S_new[k] == j:
					pass
				elif S_new[k] in vowels and j in vowels:
					m += 2
				elif S_new[k] not in vowels and j not in vowels:
					m += 2
				else:
					m += 1
		if m < x:
			x = m
	count += x
	stdout.write(f'{count}\n')


from sys import stdin, stdout
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	p = input().strip()
	s = input().strip()
	ans = n * 2
	for i in range(26):
		c = chr(i + ord('a'))
		a = s[:]
		b = p[:]
		a = a.replace('?', c)
		b = b.replace('?', c)
		t = 0
		for j in range(n):
			if a[j] != b[j]:
				if a[j] in 'aeiou' and b[j] in 'aeiou':
					t += 2
				elif a[j] not in 'aeiou' and b[j] not in 'aeiou':
					t += 2
				else:
					t += 1
		ans = min(ans, t)
	print(ans)


import sys
l = ['a', 'e', 'i', 'o', 'u']
co = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

def func(s1, s2, c):
	count = 0
	for i in range(len(s1)):
		if s1[i] == '?':
			s1[i] = c
		if s2[i] == '?':
			s2[i] = c
	for i in range(len(s1)):
		if s1[i] != s2[i]:
			if s1[i] not in l and s2[i] not in l:
				count = count + 2
			elif s1[i] in l and s2[i] in l:
				count = count + 2
			else:
				count = count + 1
	return count
n = int(input())
for i in range(n):
	n1 = int(input())
	s1 = input()
	s2 = input()
	temp = sys.maxsize
	for k in co:
		count1 = func(list(s1), list(s2), k)
		temp = min(temp, count1)
	print(temp)


def swap(s, p, N):
	mins = float('inf')
	d = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}
	for i in range(97, 123):
		S = s.replace('?', chr(i))
		P = p.replace('?', chr(i))
		count = 0
		for i in range(N):
			if S[i] != P[i]:
				if S[i] in d:
					if P[i] in d:
						count += 2
					else:
						count += 1
				elif P[i] in d:
					count += 1
				else:
					count += 2
		mins = min(count, mins)
	return mins
t = int(input().strip())
while t:
	N = int(input().strip())
	S = input().strip()
	P = input().strip()
	print(swap(S, P, N))
	t -= 1


import math
vowels = ['a', 'e', 'i', 'o', 'u']

def value(a, b):
	if a == b:
		return 0
	else:
		first = True if a in vowels else False
		second = True if b in vowels else False
		if second == first:
			return 2
		else:
			return 1

def change(a, b, tempc):
	if a == '?':
		return value(tempc, b)
	else:
		return value(tempc, a)
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	p = input()
	count = 0
	for i in range(n):
		if s[i] == p[i]:
			continue
		elif s[i] == '?' or p[i] == '?':
			continue
		else:
			count += value(s[i], p[i])
	min_count = math.inf
	for i in range(26):
		temp_char = chr(97 + i)
		count_ = 0
		for i in range(n):
			if s[i] == p[i]:
				continue
			elif s[i] == '?' or p[i] == '?':
				count_ += change(s[i], p[i], temp_char)
		min_count = min(count_, min_count)
	print(count + min_count)


vowels = ['a', 'e', 'i', 'o', 'u']

def is_vowel(c):
	return c in vowels
for _ in range(int(input())):
	n = int(input())
	s = input()
	p = input()
	ans = 1000000
	for ci in range(26):
		c = chr(ord('a') + ci)
		s2 = s.replace('?', c)
		p2 = p.replace('?', c)
		ops = 0
		for (si, pi) in zip(s2, p2):
			if si == pi:
				continue
			ops += 2 if is_vowel(si) == is_vowel(pi) else 1
		ans = min(ans, ops)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	p = input()
	if s == p:
		print(0)
		continue

	def func(c, s, p, n):
		v = set(['a', 'e', 'i', 'o', 'u'])
		ans = 0
		for i in range(n):
			a = s[i]
			b = p[i]
			if s[i] == '?':
				a = c
			if p[i] == '?':
				b = c
			if a == b:
				continue
			if a in v and b in v:
				ans += 2
			elif a not in v and b not in v:
				ans += 2
			elif a in v and b not in v:
				ans += 1
			elif a not in v and b in v:
				ans += 1
		return ans
	val = 1000000000
	for i in range(0, 26):
		val = min(val, func(chr(ord('a') + i), s, p, n))
	print(val)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	p = input()
	count1 = 0
	vowel = {'a', 'e', 'i', 'o', 'u'}
	arr = []
	for j in range(n):
		if s[j] == '?' and p[j] == '?':
			continue
		elif s[j] != '?' and p[j] != '?':
			if s[j] != p[j]:
				if s[j] in vowel:
					if p[j] in vowel:
						count1 += 2
					else:
						count1 += 1
				elif p[j] in vowel:
					count1 += 1
				else:
					count1 += 2
		elif s[j] == '?' or p[j] == '?':
			arr.append(j)
	if len(arr) != 0:
		count2 = 2 * n
		for i in range(97, 123):
			char = chr(i)
			count = 0
			for k in arr:
				flag = s[k]
				if s[k] == '?':
					flag = p[k]
				if flag != char:
					if flag in vowel:
						if char in vowel:
							count += 2
						else:
							count += 1
					elif char in vowel:
						count += 1
					else:
						count += 2
			count2 = min(count2, count)
		count1 += count2
	print(count1)


vowel = 'aeiou'
for _ in range(int(input())):
	length = int(input())
	s = input()
	p = input()
	counts = []
	for letter in range(97, 123):
		s1 = s.replace('?', chr(letter), length)
		p1 = p.replace('?', chr(letter), length)
		count = 0
		for ind in range(length):
			if s1[ind] == p1[ind]:
				pass
			elif (s1[ind] in vowel) == (p1[ind] in vowel):
				count += 2
			else:
				count += 1
		counts.append(count)
	print(min(counts))


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	v = 'aeiou'
	c = []
	for x in range(97, 123):
		s3 = s1.replace('?', chr(x))
		s4 = s2.replace('?', chr(x))
		cnt = 0
		for i in range(n):
			if s3[i] == s4[i]:
				pass
			elif s3[i] in v and s4[i] not in v:
				cnt += 1
			elif s3[i] not in v and s4[i] in v:
				cnt += 1
			else:
				cnt += 2
		c.append(cnt)
	print(min(c))


for i in range(int(input())):
	A = ['a', 'e', 'i', 'o', 'u']
	n = int(input())
	a = input()
	b = input()
	ans = 10 ** 9 + 1
	for i in range(97, 123):
		char = chr(i)
		x = a
		y = b
		p = x.replace('?', char)
		s = y.replace('?', char)
		res = 0
		for i in range(n):
			if s[i] != p[i]:
				if s[i] in A:
					if p[i] in A:
						res += 2
					else:
						res += 1
				elif p[i] not in A:
					res += 2
				else:
					res += 1
		res = min(res, ans)
		ans = res
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	p1 = input()
	k = []
	vowel = 'aeiou'
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	for x in alpha:
		(s, p) = (s1, p1)
		s = s.replace('?', x)
		p = p.replace('?', x)
		c = 0
		for i in range(n):
			if s[i] != p[i]:
				if s[i] in vowel and p[i] in vowel or (s[i] not in vowel and p[i] not in vowel):
					c += 2
				else:
					c += 1
			else:
				continue
		k.append(c)
	print(min(k))


for _ in range(int(input())):
	n = int(input())
	A = input()
	B = input()
	nc = 0
	ans = 0
	nv = 0
	f = {}
	d = {}
	W = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}
	for i in range(n):
		if A[i] == '?' and B[i] != '?':
			try:
				W[B[i]]
				nv += 1
				try:
					f[B[i]] += 1
				except:
					f[B[i]] = 1
			except:
				nc += 1
				try:
					d[B[i]] += 1
				except:
					d[B[i]] = 1
		elif B[i] == '?' and A[i] != '?':
			try:
				W[A[i]]
				nv += 1
				try:
					f[A[i]] += 1
				except:
					f[A[i]] = 1
			except:
				nc += 1
				try:
					d[A[i]] += 1
				except:
					d[A[i]] = 1
		elif A[i] != '?' and B[i] != '?':
			if A[i] == B[i]:
				pass
			else:
				try:
					W[A[i]]
					W[B[i]]
					ans += 2
				except:
					try:
						W[A[i]]
						ans += 1
					except:
						try:
							W[B[i]]
							ans += 1
						except:
							ans += 2
	if nc != 0:
		ke = max(d, key=d.get)
	if nv != 0:
		ky = max(f, key=f.get)
	if nc > 0 and nv > 0:
		ans += min(nv + (nc - d[ke]) * 2, nc + (nv - f[ky]) * 2)
	elif nc > 0:
		ans += min(nv + (nc - d[ke]) * 2, nc + nv * 2)
	elif nv > 0:
		ans += min(nv + nc * 2, nc + (nv - f[ky]) * 2)
	print(ans)


def solution():
	N = int(input())
	S = input()
	P = input()
	vowels = {'a', 'e', 'i', 'o', 'u'}
	minO = float('inf')
	for char in range(97, 122):
		alpha = chr(char)
		curO = 0
		for (s, p) in zip(S, P):
			if s == '?':
				s = alpha
			if p == '?':
				p = alpha
			if s == p:
				continue
			curO += 1 if (s in vowels) != (p in vowels) else 2
		minO = min(curO, minO)
	print(minO)
for _ in range(int(input())):
	solution()


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	p1 = input()
	count = []
	for i in 'abcdefghijklmnopqrstuvwxyz':
		count1 = 0
		s = s1
		p = p1
		s = s.replace('?', i)
		p = p.replace('?', i)
		for j in range(n):
			if s[j] != p[j]:
				if s[j] in 'aeiou' and p[j] not in 'aeiou':
					count1 += 1
				elif s[j] not in 'aeiou' and p[j] in 'aeiou':
					count1 += 1
				else:
					count1 += 2
		count.append(count1)
	print(min(count))


for _ in range(int(input())):
	n = int(input())
	ss = input()
	pp = input()
	vov = 'aeiou'
	if ss == pp:
		print(0)
	else:
		alphs = [chr(i) for i in range(97, 123)]
		orops = 9999999999
		for j in range(len(alphs)):
			aa = ss
			bb = pp
			aa = aa.replace('?', alphs[j])
			bb = bb.replace('?', alphs[j])
			ops = 0
			for i in range(n):
				if aa[i] == bb[i]:
					continue
				if aa[i] in vov and bb[i] not in vov:
					ops += 1
				elif aa[i] not in vov and bb[i] in vov:
					ops += 1
				else:
					ops += 2
			orops = min(orops, ops)
			if orops == 0:
				break
		print(orops)


def swap(P, S):
	mins = float('inf')
	vow = ['a', 'e', 'i', 'o', 'u']
	for i in range(97, 123):
		s = S[:]
		p = P[:]
		c = 0
		s = s.replace('?', chr(i))
		p = p.replace('?', chr(i))
		for (x, y) in zip(p, s):
			if x != y:
				if x in vow and y in vow:
					c += 2
				elif x not in vow and y not in vow:
					c += 2
				else:
					c += 1
		mins = min(mins, c)
	return mins
T = int(input())
while T:
	N = int(input())
	S = input()
	P = input()
	print(swap(P, S))
	T -= 1


vowels = 'aeiou'
alpha = 'abcdefghijklmnopqrstuvwxyz'

def isvowel(a):
	if a in vowels:
		return True
	else:
		return False

def main():
	t = int(input())
	for _ in range(t):
		ans = 10 ** 9
		n = int(input())
		s = str(input())
		p = str(input())
		for c in alpha:
			curr = 0
			for i in range(n):
				si = c if s[i] == '?' else s[i]
				pi = c if p[i] == '?' else p[i]
				if si == pi:
					continue
				curr += 1 if isvowel(si) != isvowel(pi) else 2
			ans = min(ans, curr)
		print(ans)
main()


t = int(input())
for i in range(0, t):
	x = int(input())
	vo = ['a', 'e', 'i', 'o', 'u']
	al = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
	li = input()
	ri = input()
	min = 1000000000000
	for j in range(0, len(al)):
		mi = li.replace('?', al[j])
		pi = ri.replace('?', al[j])
		count = 0
		for k in range(0, len(li)):
			if mi[k] == pi[k]:
				count = count + 0
			elif mi[k] in 'aeiou' and pi[k] in 'aeiou' or (mi[k] not in 'aeiou' and pi[k] not in 'aeiou'):
				count = count + 2
			else:
				count = count + 1
		if count < min:
			min = count
	print(min)


for _ in range(int(input())):
	ans = 0
	n = int(input())
	s = input()
	p = input()
	vowels = ['a', 'e', 'i', 'o', 'u']
	d = dict()
	for i in range(26):
		d[chr(ord('a') + i)] = 0
	if s == p:
		print(0)
	else:
		ans = 2 * n
		m = n
		t1 = ''
		t2 = ''
		ans1 = 0
		for i in range(n):
			if s[i] == '?' and p[i] == '?':
				continue
			if s[i] == '?' or p[i] == '?':
				t1 += s[i]
				t2 += p[i]
				continue
			if s[i] == p[i]:
				continue
			if s[i] in vowels and p[i] in vowels:
				ans1 += 2
			elif s[i] not in vowels and p[i] not in vowels:
				ans1 += 2
			else:
				ans1 += 1
		m = len(t1)
		for i in range(26):
			s1 = t1
			temp = chr(ord('a') + i)
			s1 = s1.replace('?', temp)
			p1 = t2
			p1 = p1.replace('?', temp)
			val = 0
			for j in range(m):
				v1 = s1[j] in vowels
				v2 = p1[j] in vowels
				if s1[j] != p1[j]:
					if v1 is True and v2 is True:
						val += 2
					elif v1 is False and v2 is False:
						val += 2
					else:
						val += 1
			if val < ans:
				ans = val
		ans += ans1
		print(ans)


t = int(input())
for i in range(t):
	r = int(input())
	a = input()
	b = input()
	ans = 0
	up = 0
	x = 0
	mv = 0
	mc = 0
	v = ['a', 'e', 'i', 'o', 'u']
	hh = [0] * 26
	for i in range(r):
		if a[i] == '?' or b[i] == '?':
			if a[i] == '?' and b[i] == '?':
				up -= 1
			up += 1
			if a[i] in v or b[i] in v:
				x += 1
			if a[i] != '?':
				hh[ord(a[i]) - ord('a')] += 1
				if a[i] in v:
					mv = max(mv, hh[ord(a[i]) - ord('a')])
				else:
					mc = max(mc, hh[ord(a[i]) - ord('a')])
			if b[i] != '?':
				hh[ord(b[i]) - ord('a')] += 1
				if b[i] in v:
					mv = max(mv, hh[ord(b[i]) - ord('a')])
				else:
					mc = max(mc, hh[ord(b[i]) - ord('a')])
		elif a[i] == b[i]:
			ans += 0
		elif a[i] in v and b[i] in v:
			ans += 2
		elif a[i] not in v and b[i] not in v:
			ans += 2
		else:
			ans += 1
	ans = ans + min(2 * (x - mv) + (up - x), 2 * (up - x - mc) + x)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	p = input()
	vow = 'aeiou'
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	l = []
	for e in alpha:
		sum = 0
		p2 = p.replace('?', e)
		s2 = s.replace('?', e)
		for i in range(n):
			if p2[i] != s2[i]:
				if p2[i] in vow:
					if s2[i] in vow:
						sum = sum + 2
					else:
						sum = sum + 1
				elif s2[i] in vow:
					sum = sum + 1
				else:
					sum = sum + 2
		l.append(sum)
	m = min(l)
	print(m)


for i in range(int(input())):
	n = int(input())
	s = input()
	p = input()
	d = s
	e = p
	arr = []
	co = ['a', 'e', 'i', 'o', 'u']
	alphabet_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
	for j in alphabet_list:
		s = d
		p = e
		c = 0
		s = s.replace('?', j)
		p = p.replace('?', j)
		for i in range(n):
			if s[i] == p[i]:
				pass
			elif s[i] in 'aeiou' and p[i] not in 'aeiou':
				c += 1
			elif p[i] in 'aeiou' and s[i] not in 'aeiou':
				c += 1
			else:
				c += 2
		arr.append(c)
	print(min(arr))


t = int(input())
li = ['a', 'e', 'i', 'o', 'u']
for z in range(t):
	n = int(input())
	mi = 1000000
	s = input()
	p = input()
	for j in range(26):
		cha = chr(j + 97)
		c = 0
		s1 = s.replace('?', cha)
		p1 = p.replace('?', cha)
		for i in range(n):
			if s1[i] != p1[i]:
				if (s1[i] in li) ^ (p1[i] in li):
					c = c + 1
				else:
					c = c + 2
		if c < mi:
			mi = c
	print(mi)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	s = input()
	p = input()
	vowel = defaultdict(lambda : 0)
	(vowel['a'], vowel['e'], vowel['i'], vowel['o'], vowel['u']) = (1, 1, 1, 1, 1)
	ans = 2 * n
	ooo = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
	for j in ooo:
		c = j
		k = 0
		for i in range(n):
			if s[i] == '?':
				si = c
			else:
				si = s[i]
			if p[i] == '?':
				pi = c
			else:
				pi = p[i]
			if si == pi:
				continue
			if vowel[si] != vowel[pi]:
				k += 1
			else:
				k += 2
		ans = min(ans, k)
	print(ans)


def is_vowel(s: str):
	if s in 'aeiou':
		return 'v'
	elif s == '?':
		return '?'
	else:
		return 'c'

def compare_strings(string_p, string_s) -> int:
	count = count2 = 0
	count1 = None
	comp_p = comp_s = ''
	letters_p = letters_s = ''
	vowels = not_vowels = 0
	counts_let = dict()
	for i in range(len(string_p)):
		if string_p[i] == string_s[i]:
			continue
		elif string_p[i] == '?' or string_s[i] == '?':
			comp_p += string_p[i]
			comp_s += string_s[i]
			letters_p += is_vowel(string_p[i])
			letters_s += is_vowel(string_s[i])
		else:
			count = count + 2 if is_vowel(string_p[i]) is is_vowel(string_s[i]) else count + 1
	if comp_p:
		for let in comp_p[:]:
			counts_let[let] = 1 if let not in list(counts_let) else counts_let[let] + 1
		for let in comp_s[:]:
			counts_let[let] = counts_let.get(let, 0) + 1
		counts_let.pop('?')
		if len(comp_p) == 1:
			return count
		let_to_replace = max(counts_let, key=counts_let.get)
		vowels = letters_p.count('v') + letters_s.count('v')
		not_vowels = letters_p.count('c') + letters_s.count('c')
		if counts_let[let_to_replace] > 1:
			assert_p = comp_p.replace('?', let_to_replace)
			assert_s = comp_s.replace('?', let_to_replace)
			count1 = compare_strings(assert_p, assert_s)
		if vowels >= not_vowels:
			if not_vowels != 0:
				ind = letters_p.find('c')
				if ind == -1:
					ind = letters_s.find('c')
					repl = comp_s[ind]
				else:
					repl = comp_p[ind]
			else:
				repl = 'b'
			assert_p = comp_p.replace('?', repl)
			assert_s = comp_s.replace('?', repl)
			count2 = compare_strings(assert_p, assert_s)
		else:
			if vowels != 0:
				ind = letters_p.find('v')
				if ind == -1:
					ind = letters_s.find('v')
					repl = comp_s[ind]
				else:
					repl = comp_p[ind]
			else:
				repl = 'a'
			assert_p = comp_p.replace('?', repl)
			assert_s = comp_s.replace('?', repl)
			count2 = compare_strings(assert_p, assert_s)
		if count1 is None:
			count += count2
		else:
			count += min(count1, count2)
	return count
T = int(input())
import string
for tc in range(T):
	curr_cnt = -1
	num_of_letters = int(input())
	STR_S = input()
	STR_P = input()
	if not ('?' in STR_S or '?' in STR_P):
		cnt = compare_strings(STR_P, STR_S)
	else:
		for char in string.ascii_lowercase:
			assert_s = STR_S.replace('?', char)
			assert_p = STR_P.replace('?', char)
			cnt = compare_strings(assert_p, assert_s)
			curr_cnt = cnt if curr_cnt == -1 else min(curr_cnt, cnt)
		cnt = curr_cnt
	print(cnt)


from sys import stdin, stdout
inp_num = lambda : int(input())
inp_lis = lambda : list(map(int, input().split()))
vow = {'a', 'e', 'i', 'o', 'u'}
for _ in range(inp_num()):
	n = inp_num()
	s = input()
	s1 = input()
	d = {}
	nv = 0
	nc = 0
	sc = 0
	ma = 0
	li = list(s + s1)
	for i in li:
		if i != '?':
			d[i] = 0
	for i in range(n):
		a = s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u')
		b = s1[i] == 'a' or s1[i] == 'e' or s1[i] == 'i' or (s1[i] == 'o') or (s1[i] == 'u')
		if s[i] == '?' and s1[i] == '?':
			continue
		elif s[i] == '?' or s1[i] == '?':
			if s[i] == '?':
				if b:
					nv += 1
				else:
					nc += 1
				d[s1[i]] += 1
			else:
				if a:
					nv += 1
				else:
					nc += 1
				d[s[i]] += 1
		elif a:
			if b:
				if s[i] != s1[i]:
					sc += 2
				else:
					continue
			else:
				sc += 1
		elif b:
			sc += 1
		elif s1[i] == s[i]:
			continue
		else:
			sc += 2
	p = q = 0
	for i in d.keys():
		if i in vow:
			if p < d[i]:
				p = d[i]
		elif q < d[i]:
			q = d[i]
	vowe = (nv - p) * 2 + nc
	cons = nv + (nc - q) * 2
	print(sc + min(vowe, cons))


def check(c1, c2):
	s = 'bcdfghjklmnpqrstvwxyz'
	if c1 == c2:
		return 0
	elif c1 in 'aeiou' and c2 in 'aeiou' or (c1 in s and c2 in s):
		return 2
	else:
		return 1

def compute(c1, c2):
	if len(c1) == 0:
		return 0
	minval = float('inf')
	for x in 'abcdefghijklmnopqrstuvwxyz':
		str1 = ''
		str2 = ''
		for i in range(len(c1)):
			if c1[i] == '?' and c2[i] != '?':
				str1 += x
				str2 += c2[i]
			elif c1[i] != '?' and c2[i] == '?':
				str2 += x
				str1 += c1[i]
			else:
				str1 += c1[i]
				str2 += c2[i]
		cc = 0
		for i in range(len(c1)):
			cc += check(str1[i], str2[i])
		if cc < minval:
			minval = cc
	return minval
for _ in range(int(input())):
	num = int(input())
	stt = input()
	ptt = input()
	answer = num
	string = 'abcdefghijklmnopqrstuvwxyz'
	str1 = ''
	str2 = ''
	for i in range(num):
		if stt[i] == ptt[i]:
			answer -= 1
		elif stt[i] in string and ptt[i] in string:
			if check(stt[i], ptt[i]) == 2:
				answer += 1
		else:
			answer -= 1
			str1 += stt[i]
			str2 += ptt[i]
	print(answer + compute(str1, str2))


def most_frequent(List):
	counter = 0
	num = List[0]
	for i in List:
		curr_frequency = List.count(i)
		if curr_frequency > counter:
			counter = curr_frequency
			num = i
	return num
n = int(input())
for _ in range(n):
	l = int(input())
	s1 = input()
	s2 = input()
	alls = 'abcdefghijklmnopqrstuvwxyz'
	vovels = 'aeiou'
	c = []
	for j in alls:
		x1 = ''
		x2 = ''
		count = 0
		for i in range(len(s1)):
			if s1[i] == '?':
				si = j
			else:
				si = s1[i]
			if s2[i] == '?':
				pi = j
			else:
				pi = s2[i]
			if si == pi:
				continue
			elif si in vovels and pi in vovels:
				count += 2
			elif si not in vovels and pi not in vovels:
				count += 2
			else:
				count += 1
		c.append(count)
	print(min(c))


T = int(input())
for tc in range(T):
	N = int(input())
	s = input()
	p = input()
	vow = 'aeiou'
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	l = []
	for e in alpha:
		sum = 0
		p2 = p.replace('?', e)
		s2 = s.replace('?', e)
		for i in range(N):
			if p2[i] != s2[i]:
				if p2[i] in vow:
					if s2[i] in vow:
						sum = sum + 2
					else:
						sum = sum + 1
				elif s2[i] in vow:
					sum = sum + 1
				else:
					sum = sum + 2
		l.append(sum)
	m = min(l)
	print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input().strip()
	b = input().strip()
	ans = 0
	vows = {'a', 'e', 'i', 'o', 'u'}
	s1 = ''
	s2 = ''
	for i in range(n):
		if a[i] != b[i]:
			if a[i] != '?' and b[i] != '?':
				m = a[i] in vows
				n = b[i] in vows
				if m ^ n:
					ans += 1
				else:
					ans += 2
			else:
				s1 += a[i]
				s2 += b[i]
	min_c = float('inf')
	for i in range(26):
		c = chr(ord('a') + i)
		temp = 0
		for i in range(len(s1)):
			if s1[i] == '?':
				k = s2[i]
			else:
				k = s1[i]
			if k != c:
				m = k in vows
				n = c in vows
				if m ^ n:
					temp += 1
				else:
					temp += 2
		min_c = min(min_c, temp)
	print(ans + min_c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	t = input()
	res = 0
	vow = 'aeiou'
	freq = [0] * 26
	for i in range(n):
		if s[i] == t[i]:
			continue
		if s[i] != '?' and t[i] != '?':
			if s[i] in vow and t[i] in vow:
				res += 2
			elif s[i] not in vow and t[i] not in vow:
				res += 2
			else:
				res += 1
		elif s[i] != '?':
			freq[ord(s[i]) - 97] += 1
		else:
			freq[ord(t[i]) - 97] += 1
	m1 = 999999999
	vowc = 0
	c = 0
	for i in range(26):
		if chr(i + 97) in vow:
			vowc += freq[i]
		else:
			c += freq[i]
	for i in range(26):
		if chr(i + 97) in vow:
			m1 = min(m1, 2 * (vowc - freq[i]) + c)
		else:
			m1 = min(m1, 2 * (c - freq[i]) + vowc)
	if m1 != 999999999:
		res += m1
	print(res)


def min_dico(dico):
	mini = dico['a']
	for i in alphabet:
		if dico[i] < mini:
			mini = dico[i]
	return mini
T = int(input())
alphabet = ['a', 'z', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', 'q', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'w', 'x', 'c', 'v', 'b', 'n']
consonne = ['z', 'r', 't', 'y', 'p', 'q', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'w', 'x', 'c', 'v', 'b', 'n']
voyelle = ['a', 'e', 'i', 'o', 'u']
for i in range(T):
	N = int(input())
	s = [j for j in input()]
	p = [j for j in input()]
	tot = 0
	dic = {'a': 0, 'z': 0, 'e': 0, 'r': 0, 't': 0, 'y': 0, 'u': 0, 'i': 0, 'o': 0, 'p': 0, 'q': 0, 's': 0, 'd': 0, 'f': 0, 'g': 0, 'h': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'w': 0, 'x': 0, 'c': 0, 'v': 0, 'b': 0, 'n': 0}
	for j in range(N):
		if p[j] != '?' and s[j] != '?':
			if p[j] != s[j]:
				if s[j] in voyelle:
					if p[j] in voyelle:
						tot += 2
					else:
						tot += 1
				elif not p[j] in voyelle:
					tot += 2
				else:
					tot += 1
		elif p[j] == '?':
			if s[j] in voyelle:
				for k in consonne:
					dic[k] += 1
				for k in voyelle:
					dic[k] += 2
				dic[s[j]] -= 2
			if s[j] in consonne:
				for k in consonne:
					dic[k] += 2
				for k in voyelle:
					dic[k] += 1
				dic[s[j]] -= 2
		elif s[j] == '?':
			if p[j] in voyelle:
				for k in consonne:
					dic[k] += 1
				for k in voyelle:
					dic[k] += 2
				dic[p[j]] -= 2
			if p[j] in consonne:
				for k in consonne:
					dic[k] += 2
				for k in voyelle:
					dic[k] += 1
				dic[p[j]] -= 2
	print(tot + min_dico(dic))