Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

Chef is taking a cooking exam. The exam consists of $N$ multiple-choice questions numbered $1$ through $N$. In each question, Chef may choose one out of four choices: A, B, C and D, or leave the question unanswered.

Answering a question correctly gives Chef $1$ point. Not answering a question or answering it incorrectly gives him $0$ points. However, there is a penalty for wrong answers. Specifically, the questions are graded one by one from question $1$ to question $N$; for each $i$ ($1 ≤ i ≤ N-1$), if Chef answered the $i$-th question incorrectly, his answer to the next question (the $(i+1)$-th question) is discarded without being graded. If an answer is discarded, Chef gets $0$ points for it automatically, but even if it was wrong, the next answer is not discarded. There is no penalty for answering the last question incorrectly or for not answering some questions.

You are given the correct answers to all $N$ questions and Chef's answers. Calculate the total number of points Chef scored on the exam.

------  Input ------
The first line of the 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 a single integer $N$.
The second line contains a single string $S$ with length $N$. For each valid $i$, the $i$-th character of this string denotes the correct answer to the $i$-th question.
The third line contains a single string $U$ with length $N$. For each valid $i$, the $i$-th character of this string is 'N' if Chef did not answer the $i$-th question; otherwise, it denotes Chef's answer to this question.

------  Output ------
For each test case, print a single line containing one integer — Chef's score.

------  Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$
$S$ contains only characters 'A', 'B', 'C', 'D'
$U$ contains only characters 'A', 'B', 'C', 'D', 'N'

----- Sample Input 1 ------ 
3

6

ABCDAB

ABCDAB

8

DDCABCCA

DNCBBBBA

3

CDD

NDC
----- Sample Output 1 ------ 
6

3

1
----- explanation 1 ------ 
Example case 1: Chef's answers were all correct, so he got a full score.

Example case 2: Chef did not answer question $2$ and he answered questions $4$ and $6$ incorrectly, which resulted in discarding answers to questions $5$ and $7$. Note that even though Chef's answer to question $7$ was wrong, it was discarded, so it did not result in discarding his answer to question $8$.

Example case 3: Chef did not answer the first question and he answered the last question incorrectly, but there is no penalty for that.

Source: codechef | Difficulty: EASY
Tags: Implementation


Solutions:
for i in range(int(input())):
	n = int(input())
	s = input()
	v = input()
	a = i = 0
	while i < n:
		if s[i] == v[i]:
			a += 1
			i += 1
		elif v[i] == 'N':
			i += 1
		else:
			i += 2
	print(a)


for _ in range(int(input())):
	n = int(input())
	s = input()
	u = input()
	sc = [0 if u[i] == 'N' else 1 if u[i] == s[i] else 0 if i == n - 1 else -1 for i in range(n)]
	for i in range(n - 1):
		if sc[i] == -1:
			sc[i] = 0
			sc[i + 1] = 0
	print(sum(sc))


t = int(input())
for _ in range(t):
	n = int(input())
	answers_ = input()
	answers_chef = input()
	ans = 0
	i = 0
	while i <= n - 1:
		if answers_chef[i] == answers_[i]:
			ans += 1
			i += 1
		elif i < n - 1 and answers_chef[i] != 'N':
			i += 2
		else:
			i += 1
	print(ans)


for i in range(int(input())):
	N = int(input())
	S = input()
	U = input()
	i = a = 0
	while i < N:
		if S[i] == U[i]:
			a += 1
			i += 1
		elif U[i] == 'N':
			i += 1
		else:
			i += 2
	print(a)


for _ in range(int(input())):
	N = int(input())
	S1 = input()
	S2 = input()
	score = 0
	i = 0
	while i < N:
		if S2[i] == 'N':
			i += 1
		elif S1[i] == S2[i]:
			score += 1
			i += 1
		else:
			i += 2
	print(score)


for i in range(int(input())):
	c = 0
	j = 0
	n = int(input())
	s = input()
	u = input()
	while j < n:
		if u[j] != 'N':
			if s[j] == u[j]:
				c += 1
			else:
				j = j + 1
		j = j + 1
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	l = []
	c = 0
	for i in range(n):
		if s1[i] == s2[i] and i not in l:
			c += 1
		elif s2[i] == 'N':
			pass
		elif s1[i] != s2[i] and i in l:
			pass
		elif s1[i] != s2[i]:
			l.append(i + 1)
	print(c)


for i in range(int(input())):
	n = int(input())
	s = str(input())
	u = str(input())
	i = 0
	c = 0
	while i < n:
		if s[i] == u[i]:
			c += 1
			i += 1
		elif s[i] != u[i] and u[i] != 'N':
			i += 2
		else:
			i += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	c = 0
	j = 0
	while j < n:
		if s1[j] == s2[j]:
			c = c + 1
			j = j + 1
		elif s2[j] == 'N':
			j = j + 1
			continue
		elif s1[j] != s2[j]:
			j = j + 2
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	ans = input()
	chef = input()
	wrong = False
	points = 0
	for i in range(n):
		if wrong or chef[i] == 'N':
			wrong = False
			continue
		if chef[i] == ans[i]:
			wrong = False
			points += 1
			continue
		else:
			wrong = True
	print(points)


for i in range(int(input())):
	le = int(input())
	q = input()
	a = input()
	count = 0
	i = 0
	if q == a:
		print(le)
	else:
		while i < le:
			if q[i] == a[i]:
				count += 1
				i += 1
			elif a[i] == 'N':
				i += 1
			else:
				i += 2
		print(count)


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	x = input()
	c = 0
	j = 0
	while j < n:
		if s[j] == x[j]:
			c += 1
			j += 1
		elif x[j] == 'N':
			j += 1
		else:
			j += 2
	print(c)


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	count = 0
	i = 0
	while i < n:
		if s2[i] == 'N':
			i += 1
		elif s1[i] == s2[i]:
			count += 1
			i += 1
		else:
			i += 2
	print(count)


for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	c = 0
	i = 0
	while i < n:
		if a[i] != b[i]:
			if b[i] != 'N':
				i += 1
		else:
			c += 1
		i += 1
	print(c)


for _ in range(int(input())):
	N = int(input())
	ans = input()
	chef = input()
	points = 0
	i = 0
	p = 1
	for i in range(N):
		if p == 0:
			p = 1
			continue
		if ans[i] == chef[i]:
			p = 1
			points += 1
			continue
		if chef[i] != ans[i] and chef[i] != 'N':
			p = 0
			continue
	print(points)


for t in range(int(input())):
	n = int(input())
	s = str(input())
	u = str(input())
	marks = 0
	p = 1
	for i in range(n):
		if p == 0:
			p = 1
			continue
		if s[i] == u[i]:
			marks += 1
			p = 1
			continue
		elif u[i] == 'N':
			p = 1
			continue
		else:
			p = 0
	print(marks)


for _ in range(int(input())):
	n = int(input())
	coa = input()
	cha = input()
	if coa == cha:
		print(n)
	else:
		c = 0
		i = 0
		while i < n:
			if coa[i] == cha[i]:
				c += 1
				i += 1
			elif cha[i] == 'N':
				i += 1
			else:
				i += 2
		print(c)


for i in range(int(input())):
	n = int(input())
	s = input()
	u = input()
	(flag, count) = (0, 0)
	for (x, y) in zip(s, u):
		if x == y:
			if flag == 1:
				flag = 0
			else:
				count += 1
		elif y == 'N':
			if flag == 1:
				flag = 0
			continue
		elif flag == 0:
			flag = 1
		else:
			flag = 0
	print(count)


t = int(input())
while t > 0:
	n = int(input())
	s1 = input()
	s2 = input()
	i = 0
	c = 0
	while i < n:
		if s1[i] == s2[i]:
			c = c + 1
			i = i + 1
		elif s2[i] == 'N':
			i = i + 1
		elif s1[i] != s2[i]:
			i = i + 2
	print(c)
	t = t - 1


T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	u = input()
	count = 0
	i = 0
	while i < n:
		if s[i] == u[i]:
			count += 1
		elif u[i] == 'N':
			pass
		else:
			i += 1
		i += 1
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	c = input()
	s = input()
	if c == s:
		print(n)
	else:
		count = 0
		c = list(c)
		s = list(s)
		i = 0
		while i < n:
			if s[i] == c[i]:
				count += 1
			elif s[i] == 'N':
				count += 0
			else:
				count += 0
				i += 1
			i += 1
		print(count)


for _ in range(int(input())):
	n = int(input())
	model_ans = input()
	chef_ans = input()
	discard = False
	score = 0
	for i in range(n):
		if discard:
			discard = False
		elif model_ans[i] == chef_ans[i]:
			score += 1
		elif chef_ans[i] != 'N':
			discard = True
		i += 1
	print(score)


cases = int(input())
for case in range(cases):
	questions_count = int(input())
	answer_key = input()
	chef_answers = input()
	question = 0
	score = 0
	while question < questions_count:
		if not chef_answers[question] == 'N':
			if chef_answers[question] == answer_key[question]:
				score += 1
			else:
				question += 1
		question += 1
	print(score)


t = int(input())
for i in range(t):
	n = int(input())
	sol = [item for item in input()]
	ans = [item for item in input()]
	marks = 0
	for question in range(len(ans) - 1):
		answer = ans[question]
		solution = sol[question]
		if answer != solution and answer != 'N':
			ans[question] = 'N'
			ans[question + 1] = 'N'
	for yes in range(len(ans)):
		answer = ans[yes]
		solution = sol[yes]
		if answer == solution:
			marks += 1
	print(marks)


for _ in range(int(input())):
	N = int(input())
	model = list(input().strip())
	ans = list(input().strip())
	score = 0
	penalty = False
	for (m, a) in zip(model, ans):
		if penalty:
			penalty = False
			continue
		if m == a:
			score += 1
		if a == 'N':
			continue
		if m != a:
			penalty = True
	print(score)


for _ in range(int(input())):
	n = int(input())
	a = list(input())
	b = list(input())
	m = 0
	i = 0
	while i < n:
		if a[i] == b[i]:
			m += 1
		elif b[i] != 'N':
			i += 1
		else:
			m += 0
		i += 1
	print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	S = str(input())
	U = str(input())
	count = 0
	i = 0
	while i < n:
		if S[i] == U[i]:
			count += 1
		elif U[i] == 'N':
			pass
		else:
			i = i + 1
		i += 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	ans = input()
	sheet = input()
	i = 0
	cnt = 0
	while i < n:
		if sheet[i] == ans[i]:
			cnt += 1
			i += 1
		elif sheet[i] != ans[i] and sheet[i] == 'N':
			i += 1
		elif sheet[i] != ans[i]:
			i += 2
	print(cnt)


t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	u = list(input())
	c = 0
	j = 0
	while j != len(s):
		if s[j] == u[j]:
			c += 1
		elif u[j] == 'N':
			c
		elif j == len(s) - 1:
			break
		else:
			j = j + 1
		j = j + 1
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	s = list(str(input()))
	u = list(str(input()))
	c = 0
	i = 0
	while i < n:
		if s[i] == u[i]:
			c += 1
		elif u[i] == 'N':
			pass
		else:
			i += 1
		i += 1
	print(c)


for i in range(int(input())):
	N = int(input())
	S = input()
	U = input()
	(c, i) = (0, 0)
	while i < N:
		if S[i] == U[i]:
			c += 1
		elif U[i] == 'N':
			pass
		else:
			i = i + 1
		i += 1
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	str1 = input()
	str2 = input()
	i = 0
	count = 0
	while i < n:
		if str1[i] == str2[i]:
			count += 1
			i = i + 1
		elif str2[i] == 'N':
			i = i + 1
		elif str1[i] != str2[i]:
			i = i + 2
	print(count)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	u = list(input())
	(c, i) = (0, 0)
	while i <= n - 1:
		if u[i] == 'N':
			i += 1
			continue
		elif u[i] == s[i]:
			c += 1
			i += 1
		else:
			i += 2
	print(c)


t = int(input())
while t != 0:
	n = int(input())
	a = input()
	c = input()
	p = i = 0
	while i < n:
		if a[i] == c[i]:
			p += 1
			i += 1
		elif c[i] == 'N':
			i += 1
		else:
			i += 2
	print(p)
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	r = 0
	ranswers = input()
	answers = input()
	i = 0
	penalty = False
	while i < n:
		if penalty:
			i += 1
			penalty = False
			continue
		elif 'N' == answers[i]:
			penalty = False
		elif answers[i] == ranswers[i] and (not penalty or i == n - 1):
			r += 1
		elif answers[i] != ranswers[i]:
			penalty = True
		i += 1
	print(r)
	t -= 1


for _ in range(int(input())):
	N = int(input())
	S = input()
	U = input()
	(Points, Not_ans) = (0, 0)
	for i in range(N):
		if Not_ans == 1:
			Not_ans = 0
		elif S[i] == U[i]:
			Points += 1
			Not_ans = 0
		elif U[i] == 'N':
			Not_ans += 0
		else:
			Not_ans += 1
	print(Points)


for tc in range(int(input())):
	n = int(input())
	s = input()
	u = input()
	(disc, points) = (0, 0)
	for i in range(n):
		if disc == 1:
			disc = 0
		elif s[i] == u[i]:
			points += 1
			disc = 0
		elif u[i] == 'N':
			disc = 0
		else:
			disc = 1
	print(points)


for _ in range(int(input())):
	n = int(input())
	s = input()
	u = input()
	pt = 0
	score = 0
	while pt < n:
		if s[pt] == u[pt]:
			score += 1
			pt += 1
		elif u[pt] == 'N':
			pt += 1
		else:
			pt += 2
	print(score)


n = int(input())
for i in range(n):
	flag = 0
	qs = int(input())
	key = list(input())
	res = list(input())
	for q in range(qs - 1):
		if key[q] != res[q] and res[q] != 'N' and (res[q] != 'M'):
			res[q + 1] = 'M'
	for q in range(qs):
		if key[q] == res[q]:
			flag = flag + 1
	print(flag)


for t in range(int(input())):
	k = int(input())
	st1 = input()
	st2 = input()
	cn = 0
	f = 0
	while f < k:
		if st1[f] == st2[f]:
			cn += 1
		elif st2[f] == 'N':
			pass
		else:
			f += 1
		f += 1
	print(cn)


for tc in range(int(input())):
	n = int(input())
	str1 = input()
	str2 = input()
	cnt = 0
	i = 0
	while i < n:
		if str1[i] == str2[i]:
			cnt += 1
		elif str2[i] == 'N':
			pass
		else:
			i += 1
		i += 1
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	u = list(input())
	i = 0
	count = 0
	while i < n - 1:
		if s[i] == u[i]:
			count += 1
		elif u[i] != 'N':
			u[i + 1] = 'N'
		i += 1
	if s[-1] == u[-1]:
		count += 1
	print(count)


for _ in range(int(input())):
	l = int(input())
	ra = input()
	ca = input()
	(i, c) = (0, 0)
	while i < len(ra):
		if ra[i] == ca[i]:
			c += 1
			i += 1
		elif ca[i] == 'N':
			i += 1
		elif ra[i] != ca[i]:
			i += 2
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	u = input()
	i = 0
	j = 0
	while i < n:
		if s[i] == u[i]:
			j += 1
			i += 1
		elif u[i] == 'N':
			i += 1
		else:
			i += 2
	print(j)


for _ in range(int(input())):
	a = int(input())
	q = input()
	an = input()
	x = -1
	t = 0
	for _ in range(a):
		if q[_] == an[_] and _ != x:
			t += 1
		elif q[_] != an[_] and _ != x and (an[_] != 'N'):
			x = 1 + _
		else:
			pass
	print(t)


for _ in range(int(input())):
	n = int(input())
	c = input()
	a = input()
	(i, j) = (0, 0)
	while i < n:
		if a[i] == c[i]:
			j += 1
		elif a[i] == 'N':
			pass
		else:
			i += 1
		i += 1
	print(j)


def calc_marks(n, correct_s, exam_s):
	marks = 0
	i = 0
	while i < n:
		if exam_s[i] == correct_s[i]:
			marks = marks + 1
			i = i + 1
		elif exam_s[i] == 'N':
			i = i + 1
		else:
			i = i + 2
	return marks
t = int(input())
for i in range(t):
	n = int(input())
	correct_s = input()
	exam_s = input()
	print(calc_marks(n, correct_s, exam_s))