A binary string is a string that consists of characters $0$ and $1$. A bi-table is a table that has exactly two rows of equal length, each being a binary string.

Let $\operatorname{MEX}$ of a bi-table be the smallest digit among $0$, $1$, or $2$ that does not occur in the bi-table. For example, $\operatorname{MEX}$ for $\begin{bmatrix} 0011\\ 1010 \end{bmatrix}$ is $2$, because $0$ and $1$ occur in the bi-table at least once. $\operatorname{MEX}$ for $\begin{bmatrix} 111\\ 111 \end{bmatrix}$ is $0$, because $0$ and $2$ do not occur in the bi-table, and $0 < 2$.

You are given a bi-table with $n$ columns. You should cut it into any number of bi-tables (each consisting of consecutive columns) so that each column is in exactly one bi-table. It is possible to cut the bi-table into a single bi-table — the whole bi-table.

What is the maximal sum of $\operatorname{MEX}$ of all resulting bi-tables can be?


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.

The first line of the description of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of columns in the bi-table.

Each of the next two lines contains a binary string of length $n$ — the rows of the bi-table.

It's guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case print a single integer — the maximal sum of $\operatorname{MEX}$ of all bi-tables that it is possible to get by cutting the given bi-table optimally.


-----Examples-----

Input
4
7
0101000
1101100
5
01100
10101
2
01
01
6
000000
111111
Output
8
8
2
12


-----Note-----

In the first test case you can cut the bi-table as follows:

$\begin{bmatrix} 0\\ 1 \end{bmatrix}$, its $\operatorname{MEX}$ is $2$.

$\begin{bmatrix} 10\\ 10 \end{bmatrix}$, its $\operatorname{MEX}$ is $2$.

$\begin{bmatrix} 1\\ 1 \end{bmatrix}$, its $\operatorname{MEX}$ is $0$.

$\begin{bmatrix} 0\\ 1 \end{bmatrix}$, its $\operatorname{MEX}$ is $2$.

$\begin{bmatrix} 0\\ 0 \end{bmatrix}$, its $\operatorname{MEX}$ is $1$.

$\begin{bmatrix} 0\\ 0 \end{bmatrix}$, its $\operatorname{MEX}$ is $1$.

The sum of $\operatorname{MEX}$ is $8$.

Source: codeforces | Difficulty: EASY
Tags: Dynamic programming

Bit manipulation

Constructive algorithms

Greedy algorithms


Solutions:
import sys
import math
import heapq
from collections import defaultdict as dd
from collections import OrderedDict as od
from collections import deque
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key as ctk
from functools import lru_cache
from bisect import bisect_left as bs_l
from bisect import bisect_right as bs_r
input = sys.stdin.readline
mod = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)

def comparator(x, y):
	if x[0] == y[0]:
		return y[1] - x[1]
	return True

def ncr(n, r):
	if n < r:
		return 0
	return fc[n] * pow(fc[r] * fc[n - r] % mod, mod - 2, mod) % mod
T = int(input())
for _ in range(T):
	n = int(input())
	s1 = input().strip()
	s2 = input().strip()
	ans = 0
	(f0, f1) = (0, 0)
	for i in range(n):
		if s1[i] == '0' and s2[i] == '1' or (s1[i] == '1' and s2[i] == '0'):
			ans += 2
			if f0:
				ans += f0
			(f0, f1) = (0, 0)
		elif s1[i] == s2[i] == '0':
			if f1:
				ans += 2
				(f0, f1) = (0, 0)
			else:
				f0 += 1
		elif f0:
			ans += 2
			f0 -= 1
			if f0:
				ans += f0
			(f0, f1) = (0, 0)
		else:
			f1 += 1
	ans += f0
	print(ans)


t = int(input())
for T in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	i = 0
	ans = 0
	while i < n:
		if s1[i] == '0' and s2[i] == '1':
			ans += 2
			i += 1
		elif s1[i] == '1' and s2[i] == '0':
			ans += 2
			i += 1
		elif s1[i] == '0' and s2[i] == '0':
			if i + 1 < n and s1[i + 1] == '1' and (s2[i + 1] == '1'):
				ans += 2
				i += 2
			else:
				ans += 1
				i += 1
		else:
			temp = 0
			for j in range(i + 1, n, 1):
				if s1[i] == '1' and (s1[j] == '0' or s2[j] == '0'):
					ans += 2
					temp = j
					break
				else:
					break
			if temp != 0:
				i = temp + 1
			else:
				i += 1
	print(ans)


cnt = int(input())
for _ in range(cnt):
	(leng, s1, s2) = (int(input()), input(), input())
	(s, i) = (0, 0)
	while i < leng:
		if int(s1[i]) + int(s2[i]) == 1:
			s += 2
		elif int(s1[i]) + int(s2[i]) == 2:
			for j in range(i + 1, leng):
				i += 1
				if int(s1[i]) + int(s2[i]) <= 1:
					s += 2
					break
		elif i < leng - 1 and int(s1[i + 1]) + int(s2[i + 1]) == 2:
			s += 2
			i += 1
		else:
			s += 1
		i += 1
	print(s)


from sys import stdin, stdout
from collections import defaultdict
import math
from itertools import groupby

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

def get_int():
	return int(stdin.readline())

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

def get_string():
	return stdin.readline().strip()

def printn(n):
	stdout.write(str(n) + '\n')

def printlis(a):
	for x in a:
		stdout.write(str(x) + ' ')
	printn('')

def solve():
	n = get_int()
	a = get_string()
	b = get_string()
	ans = 0
	i = 0
	x = -1
	while i < n:
		if a[i] != b[i]:
			ans += 2
		elif a[i] == b[i] and a[i] == '1':
			if i > 0 and a[i - 1] == b[i - 1] and (a[i - 1] == '0') and (x != i - 1):
				ans += 1
			elif i < n - 1 and a[i + 1] == b[i + 1] and (a[i + 1] == '0'):
				ans += 1
				x = i + 1
		else:
			ans += 1
		i += 1
	printn(ans)
	return
t = get_int()
while t:
	t -= 1
	solve()


from itertools import groupby
for _ in range(int(input())):
	n = int(input())
	o = input()
	p = input()
	op = list(zip(o, p))
	ans = 0
	i = 0
	while i < n:
		(r1, r2) = op[i]
		if r1 != r2:
			ans += 2
			i += 1
		elif r1 == r2 == '0':
			try:
				if set(op[i + 1]) == {'1'}:
					ans += 2
					i += 2
				else:
					ans += 1
					i += 1
			except:
				ans += 1
				i += 1
		elif r1 == r2 == '1':
			try:
				if set(op[i + 1]) == {'0'}:
					ans += 2
					i += 2
				else:
					i += 1
			except:
				i += 1
	print(ans)


import sys
import math
from bisect import bisect_left
import heapq
from collections import deque
from itertools import product, permutations
import random

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

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

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

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

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
for _ in range(II()):
	n = II()
	s = list(SI())
	s1 = list(SI())
	ans = 0
	for i in range(len(s)):
		if s[i] == s1[i] == '1':
			if i != 0 and s[i - 1] == s1[i - 1] == '0':
				s[i - 1] = s1[i - 1] = ''
				s[i] = '0'
			elif i != len(s) - 1 and s[i + 1] == s1[i + 1] == '0':
				s[i] = s1[i] = ''
				s[i + 1] = '1'
	for i in range(len(s)):
		if s[i] != s1[i]:
			ans += 2
		elif s[i] == '0':
			ans += 1
	print(ans)


t = int(input())
for k in range(t):
	n = int(input())
	a = input()
	b = input()
	count = 0
	i = 0
	while i < n:
		if a[i] != b[i]:
			count += 2
			i += 1
		elif i + 1 < n:
			if a[i] == '0' and a[i + 1] == '1' and (b[i + 1] == '1'):
				count += 2
				i += 2
			elif a[i] == '1' and a[i + 1] == '0' and (b[i + 1] == '0'):
				count += 2
				i += 2
			elif a[i] == '0':
				count += 1
				i += 1
			else:
				i += 1
		elif a[i] == '0':
			count += 1
			i += 1
		else:
			i += 1
	print(count)


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	n = int(input())
	a = input().strip()
	b = input().strip()
	ans = 0
	i = 0
	while i < n:
		if a[i] != b[i]:
			ans += 2
		elif a[i] == '0':
			if i + 1 < n and a[i + 1] == '1' and (b[i + 1] == '1'):
				ans += 2
				i += 1
			else:
				ans += 1
		elif i + 1 < n and a[i + 1] == '0' and (b[i + 1] == '0'):
			ans += 2
			i += 1
		i += 1
	print(ans)
	t -= 1


import sys
import math
input = sys.stdin.readline
T = int(input())
for i in range(T):
	n = int(input())
	s1 = input()
	s2 = input()
	cnt1 = 0
	cnt0 = 0
	ans = 0
	for j in range(n):
		if s1[j] != s2[j]:
			ans += 2
			if cnt0 > 0:
				ans += cnt0
			cnt1 = 0
			cnt0 = 0
		elif s1[j] == '0':
			if cnt1 > 0:
				ans += 2
				cnt1 = 0
			else:
				cnt0 += 1
		elif cnt0 > 0:
			ans += 2 + cnt0 - 1
			cnt0 = 0
		else:
			cnt1 += 1
	ans += cnt0
	print(ans)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		r1 = input()
		r2 = input()
		sol = 0
		(prev_i, prev_j) = (None, None)
		for (i, j) in zip(r1, r2):
			if i == j == '1' and prev_i == prev_j == '0':
				sol += 1
				i = j = None
			elif i == j == '0' and prev_i == prev_j == '1':
				sol += 2
				i = j = None
			elif i == j == '0':
				sol += 1
			elif i != j:
				sol += 2
			(prev_i, prev_j) = (i, j)
		print(sol)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	c = [0] * n
	ans = 0
	for i in range(n):
		if a[i] != b[i]:
			c[i] = '2'
		else:
			c[i] = a[i]
	for i in range(n):
		if c[i] == '2':
			ans += 2
		elif c[i] == '0':
			if i > 0 and c[i - 1] == '1':
				ans += 2
			elif i < n - 1 and c[i + 1] == '1':
				ans += 2
				c[i + 1] = -1
			else:
				ans += 1
	print(ans)


import math

def median(s1, s2):
	cnt = 0
	i = 0
	j = 0
	while i < len(s1) and j < len(s2):
		if s1[i] != s2[j]:
			cnt += 2
		elif s1[i] == s2[j]:
			if i + 1 < len(s1) and j + 1 < len(s2) and (s1[i + 1] == s2[j + 1]) and (s1[i + 1] != s1[i]):
				cnt += 2
				i += 1
				j += 1
			elif s1[i] == '0':
				cnt += 1
		i += 1
		j += 1
	return cnt
t = int(input())
for i in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	print(median(s1, s2))


t = int(input())
for j in range(t):
	dl = int(input())
	stro1 = input()
	stro2 = input()
	s = 0
	act = False
	for i in range(dl):
		if int(stro1[i]) + int(stro2[i]) == 1:
			s += 2
		elif int(stro1[i]) + int(stro2[i]) == 0 and (not act):
			if i < dl - 1 and int(stro1[i + 1]) + int(stro2[i + 1]) == 2:
				act = True
				s += 2
			else:
				s += 1
		elif int(stro1[i]) + int(stro2[i]) == 2 and (not act):
			if i < dl - 1 and int(stro1[i + 1]) + int(stro2[i + 1]) == 0:
				act = True
				s += 2
		elif act is True:
			act = False
	print(s)


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	(x, y, c) = (0, 0, 0)
	ans = 0
	for i in range(n):
		if s1[i] == '1' and s2[i] == '1':
			if y == 1:
				y = 0
				ans += 2
				ans += c - 1
				c = 0
				continue
			x = 1
		elif s1[i] == '0' and s2[i] == '0':
			if x == 1:
				x = 0
				ans += 2
				c = 0
				continue
			y = 1
			c += 1
		else:
			x = 0
			y = 0
			if c > 0:
				ans += c
				c = 0
			ans += 2
	print(ans + c)


import sys, os, io
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(input().strip())
	b = list(input().strip())
	c = []
	curr = '.'
	ccnt = 0
	ans = 0
	for i in range(len(a)):
		if a[i] == b[i]:
			if a[i] == '1':
				if curr == '0':
					ans += 2 + ccnt - 1
					curr = '.'
					ccnt = 0
				else:
					curr = '1'
					ccnt += 1
			elif a[i] == '0':
				if curr == '1':
					ans += 2
					curr = '.'
					ccnt = 0
				else:
					curr = '0'
					ccnt += 1
		else:
			if curr == '0':
				ans += 2 + ccnt
			else:
				ans += 2
			curr = '.'
			ccnt = 0
	if curr == '0':
		ans += ccnt
	print(ans)


import sys
input = sys.stdin.readline

def process(n, a, b):
	ans = 0
	i = 0
	while i < n:
		if a[i] != b[i]:
			ans += 2
			i += 1
			continue
		if a[i] == '1':
			if i + 1 < n and (a[i + 1] == '0' or b[i + 1] == '0'):
				ans += 2
				i += 2
			else:
				i += 1
		elif i + 1 < n and a[i + 1] == '1' and (b[i + 1] == '1'):
			ans += 2
			i += 2
		else:
			ans += 1
			i += 1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input().rstrip()
	s2 = input().rstrip()
	print(process(n, s1, s2))


for _ in range(int(input())):
	x = int(input())
	s1 = input()
	s2 = input()
	ans = 0
	i = 0
	while i < len(s1):
		n0 = 0
		n1 = 0
		j = i
		while j < len(s1):
			if s1[j] != s2[j]:
				ans += 2
				if n0 != 0:
					ans += 1
				i = j + 1
				break
			if s1[j] == '0':
				n0 += 1
			else:
				n1 += 1
			if s2[j] == '0':
				n0 += 1
			else:
				n1 += 1
			if n0 > 0 and n1 > 0:
				ans += 2
				i = j + 1
				break
			if n0 == 0:
				j += 1
			elif n1 == 0:
				if j == len(s1) - 1:
					ans += n0 // 2
					i = j + 1
					break
				if s1[j + 1] == s2[j + 1] == '0':
					i = j + 1
					ans += 1
					break
				else:
					j += 1
		if i != j + 1:
			i = j + 1
	print(ans)


def solve(x, y):
	ans = 0
	seen0 = seen1 = False
	for (a, b) in zip(x, y):
		if a != b:
			ans += 2 + seen0
			seen0 = seen1 = False
		elif a == '0':
			if seen1:
				ans += 2
				seen0 = seen1 = False
			elif seen0:
				ans += 1
			else:
				seen0 = True
		elif seen0:
			ans += 2
			seen0 = seen1 = False
		else:
			seen1 = True
	ans += seen0
	return ans
tests = int(input())
for _ in range(tests):
	(_, x, y) = (input(), input(), input())
	print(solve(x, y))


for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, list(input())))
	arr2 = list(map(int, list(input())))
	i = 0
	ans = 0
	while i < n - 1:
		if arr1[i] == 0 and arr2[i] == 0 and (arr1[i + 1] == 1) and (arr2[i + 1] == 1):
			ans += 2
			arr1[i] = 1
			arr2[i] = 1
			arr1[i + 1] = 1
			arr2[i + 1] = 1
			i += 1
		elif arr1[i] == 1 and arr2[i] == 1 and (arr1[i + 1] == 0) and (arr2[i + 1] == 0):
			ans += 2
			arr1[i] = 1
			arr2[i] = 1
			arr1[i + 1] = 1
			arr2[i + 1] = 1
			i += 1
		i += 1
	for i in range(n):
		if arr1[i] != arr2[i]:
			ans += 2
		elif arr1[i] == 0:
			ans += 1
	print(ans)


import sys
import os
from math import ceil, floor, sqrt, gcd, factorial, log, log2
from io import BytesIO, IOBase
from collections import Counter
from itertools import permutations, combinations
from bisect import bisect
from functools import reduce
inf = int(10000000000.0)
BUFSIZE = 8192
inp = lambda : int(input())
mp = lambda : map(int, input().split())
lst = lambda : list(map(int, input().split()))

def main():
	for _ in range(inp()):
		n = inp()
		a = input()
		b = input()
		sum = 0
		skipit = False
		for i in range(n):
			if a[i] == '0' and b[i] == '1' or (a[i] == '1' and b[i] == '0'):
				sum += 2
			elif a[i] == b[i] == '0':
				if skipit:
					skipit = False
					continue
				elif i != n - 1 and a[i + 1] == b[i + 1] == '1':
					sum += 2
					skipit = True
				else:
					sum += 1
			elif skipit:
				skipit = False
				continue
			elif i != n - 1 and a[i + 1] == b[i + 1] == '0':
				skipit = True
				sum += 2
		print(sum)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


I = input
for _ in [0] * int(I()):
	I()
	r = 0
	p = 1
	for (x, y) in zip(*(map(int, I()) for _ in '__')):
		x += y
		r += (x + 1) % 3
		f = x ^ p == 2
		r += f
		p = f or x
	print(r)


import math
t = int(input())
for i in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	cnt = 0
	i = 0
	while i < len(s1):
		if s1[i] == '1' and s2[i] == '1':
			i += 1
			while i < len(s1) and s1[i] != '0' and (s2[i] != '0'):
				i += 1
			if i < len(s1):
				cnt += 2
			i += 1
		elif s1[i] == '1' and s2[i] == '0' or (s1[i] == '0' and s2[i] == '1'):
			cnt += 2
			i += 1
		else:
			i += 1
			if i < len(s1) and s1[i] == '1' and (s2[i] == '1'):
				i += 1
				cnt += 2
			else:
				cnt += 1
	print(cnt)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = int(1000000000.0) + 7

def power(k, n):
	if n == 0:
		return 1
	if n % 2:
		return power(k, n - 1) * k % mod
	t = power(k, n // 2)
	return t * t % mod

def totalPrimeFactors(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def main():
	for _ in range(int(input())):
		n = int(input())
		f = input()
		s = input()
		ans = 0
		pre = [0, 0]
		for i in range(n):
			if ord('0') <= ord(s[i]) <= ord('1'):
				if s[i] != f[i]:
					ans += 2
					for j in range(2):
						if pre[j] == 0:
							ans += j
							break
					pre = [0, 0]
				elif s[i] == '0':
					if pre[0]:
						ans += 1
					else:
						pre[0] = 1
						if pre[0] == pre[1]:
							ans += 2
							pre = [0, 0]
				elif pre[0]:
					ans += 2
					pre = [0, 0]
				else:
					pre[1] = 1
		for j in range(2):
			if pre[j] == 0:
				ans += j
				break
		print(ans)
	return
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input()))
	b = list(map(int, input()))
	flag = 0
	ref = [0] * n
	ref[0] = a[0] + b[0]
	sum = 2 if ref[0] == 1 else 1 if ref[0] == 0 else 0
	if n > 1:
		for i in range(1, n):
			ref[i] = a[i] + b[i]
			if ref[i] == 1:
				sum += 2
			elif ref[i] == 0:
				if ref[i - 1] == 2 and flag == 0:
					flag = 1
					sum += 2
				else:
					sum += 1
					flag = 0
			elif ref[i - 1] == 0 and flag == 0:
				flag = 1
				sum += 1
			else:
				flag = 0
	print(sum)


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10001)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10000):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

class LazySegUpdate:

	def __init__(self, N):
		self.N = N
		n = 4 * N
		self.tree = [0] * n
		self.lazy = [0] * n

	def queryHelper(self, index, s, e, l, r):
		if self.lazy[index]:
			update = self.lazy[index]
			self.lazy[index] = 0
			self.tree[index] = max(self.tree[index], update)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], update)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], update)
		if s > e or s > r or e < l:
			return 0
		if s >= l and e <= r:
			return self.tree[index]
		mid = (s + e) // 2
		return max(self.queryHelper(2 * index, s, mid, l, r), self.queryHelper(2 * index + 1, mid + 1, e, l, r))

	def updateHelper(self, index, s, e, l, r, h):
		if self.lazy[index]:
			update = self.lazy[index]
			self.lazy[index] = 0
			self.tree[index] = max(self.tree[index], update)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], update)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], update)
		if s > e or s > r or e < l:
			return
		if s >= l and e <= r:
			self.tree[index] = max(self.tree[index], h)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], h)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], h)
			return
		mid = (s + e) // 2
		self.updateHelper(2 * index, s, mid, l, r, h)
		self.updateHelper(2 * index + 1, mid + 1, e, l, r, h)
		self.tree[index] = max(self.tree[2 * index], self.tree[2 * index + 1])

	def query(self, l, r):
		return self.queryHelper(1, 0, self.N - 1, l, r - 1)

	def update(self, l, r, h):
		self.updateHelper(1, 0, self.N - 1, l, r - 1, h)

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = n
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = mid
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
t = 1
t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	a.append(input())
	a.append(input())
	s = set()
	ans = 0
	for i in range(n):
		s1 = set([int(a[0][i]), int(a[1][i])])
		if 0 in s:
			if len(s1) == 1:
				if 0 in s1:
					ans += 1
				else:
					ans += 2
					s = set()
			else:
				ans += 3
				s = set()
		elif 1 in s:
			if len(s1) == 1:
				if 0 in s1:
					ans += 2
					s = set()
			else:
				ans += 2
				s = set()
		elif len(s1) == 2:
			ans += 2
		else:
			s = s1
	if 0 in s:
		ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	(c, ans) = (0, 0)
	while c <= n - 1:
		if s1[c] == '0' and s2[c] == '1':
			c += 1
			ans += 2
		elif s1[c] == '1' and s2[c] == '0':
			c += 1
			ans += 2
		elif s1[c] == '0':
			if c < n - 1:
				if s1[c + 1] == '1' and s2[c + 1] == '1':
					c += 2
					ans += 2
				else:
					c += 1
					ans += 1
			else:
				ans += 1
				c += 1
		elif c < n - 1:
			if s1[c + 1] == '0' and s2[c + 1] == '0':
				c += 2
				ans += 2
			else:
				c += 1
			ans += 0
		else:
			c += 1
	print(ans)


I = input
for _ in [0] * int(I()):
	I()
	r = 0
	p = 1
	for (x, y) in zip(*(map(int, I()) for _ in '__')):
		x += y
		r += (1, 2, 0)[x]
		if {x, p} == {0, 2}:
			r += 1
			p = 1
		else:
			p = x
	print(r)


t = int(input())
for _ in range(t):
	l = int(input())
	s = input()
	m = input()
	flag = 0
	ans = 0
	for i in range(l):
		if int(s[i]) + int(m[i]) == 1 and flag == 0:
			ans += 2
			flag = 0
		elif int(s[i]) + int(m[i]) == 1 and flag == 1:
			ans += 3
			flag = 0
		if int(s[i]) + int(m[i]) == 1 and flag == 2:
			ans += 2
			flag = 0
		elif int(s[i]) + int(m[i]) == 2 and flag == 0:
			flag = 2
		elif int(s[i]) + int(m[i]) == 2 and flag == 1:
			ans += 2
			flag = 0
		elif int(s[i]) + int(m[i]) == 2 and flag == 2:
			flag = 2
		elif int(s[i]) + int(m[i]) == 0 and flag == 0:
			flag = 1
		elif int(s[i]) + int(m[i]) == 0 and flag == 1:
			flag = 1
			ans += 1
		elif int(s[i]) + int(m[i]) == 0 and flag == 2:
			ans += 2
			flag = 0
	if flag == 1:
		ans += 1
	print(ans)


tst = int(input())
for _ in range(tst):
	n = int(input())
	s = input()
	t = input()
	total = 0
	d = set()
	for i in range(n):
		if s[i] == '0' and t[i] == '0':
			total += 1
		elif s[i] == '0' and t[i] == '1':
			total += 2
		elif s[i] == '1' and t[i] == '0':
			total += 2
		elif s[i] == '1' and t[i] == '1':
			if i - 1 >= 0 and s[i - 1] == '0' and (t[i - 1] == '0') and (i - 1 not in d):
				total += 1
				d.add(i - 1)
			elif i + 1 < n and s[i + 1] == '0' and (t[i + 1] == '0') and (i + 1 not in d):
				total += 1
				d.add(i + 1)
	print(total)


from collections import Counter, deque, defaultdict
from heapq import *
import math

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

def mapInput():
	return map(int, input().split())

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

def task():
	n = inp()
	x = input()
	y = input()
	(res, i) = (0, 0)
	while i < n:
		c = defaultdict(int)
		c[x[i]] += 1
		c[y[i]] += 1
		if c['1'] > 0 and c['0'] > 0:
			res += 2
		elif i < n - 1:
			c[x[i + 1]] += 1
			c[y[i + 1]] += 1
			if c['1'] > 0 and c['0'] > 0 and (x[i + 1] == y[i + 1]):
				res += 2
				i += 1
			elif x[i] == '0' and y[i] == '0':
				res += 1
		elif c['1'] == 0:
			res += 1
		i += 1
	return res
for _ in range(inp()):
	print(task())


import math
t = int(input())
cases = []
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	cases.append((a, b))

def answer(a, b):
	ans = 0
	n = len(a)
	nextBreak = False
	for i in range(n):
		if nextBreak == True:
			nextBreak = False
			continue
		if a[i] == '0' and b[i] == '1' or (a[i] == '1' and b[i] == '0'):
			ans += 2
			continue
		if a[i] == '0' and b[i] == '0':
			if i == n - 1:
				ans += 1
				continue
			elif a[i + 1] == '1' and b[i + 1] == '1':
				nextBreak = True
				ans += 2
				continue
			else:
				ans += 1
				continue
		if a[i] == '1' and b[i] == '1':
			if i == n - 1:
				continue
			elif a[i + 1] == '0' and b[i + 1] == '0':
				nextBreak = True
				ans += 2
	return ans
for i in cases:
	print(answer(i[0], i[1]))


def can_be_paired_up(current_pair, next_pair):
	all_pairs = []
	all_pairs.extend(list(current_pair))
	all_pairs.extend(list(next_pair))
	if '01' == next_pair:
		return False
	if '0' in all_pairs and '1' in all_pairs:
		return True
	return False

def solve():
	n = int(input())
	s = [list(input()), list(input())]
	b = []
	for i in range(n):
		ss = '{}{}'.format(s[0][i], s[1][i])
		if ss[0] == '1':
			ss = '{}{}'.format(ss[1], ss[0])
		b.append(ss)
	s = b
	index = 0
	mex = 0
	while index < n:
		current = s[index]
		if '01' == current:
			mex += 2
			index += 1
			continue
		if index + 1 >= n:
			mex += 1 if '0' in current else 0
			index += 1
			continue
		next = s[index + 1]
		if can_be_paired_up(current, next):
			mex += 2
			index += 2
			continue
		mex += 1 if '0' in current else 0
		index += 1
	return mex
for _ in range(int(input())):
	print(solve())


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


def int_input():
	a = int(input())
	return a

def int_list_input():
	a = list(map(int, input().split()))
	return a

def solve():
	n = int(input())
	a = input()
	b = input()
	l = []
	for i in range(n):
		if a[i] != b[i]:
			l.append(2)
		elif a[i] == '1':
			l.append(0)
		else:
			l.append(1)
	ans = 0
	i = 0
	while i < n:
		if i + 1 < n and l[i] + l[i + 1] == 1:
			ans += 2
			i += 1
		else:
			ans += l[i]
		i += 1
	print(ans)
for _ in range(int(input())):
	solve()


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


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	d = 0
	i = 0
	while i < n:
		if a[i] != b[i]:
			d += 2
		elif a[i] == '0':
			if i + 1 < n and a[i + 1] == '1' and (b[i + 1] == '1'):
				d += 2
				i += 1
			else:
				d += 1
		elif i + 1 < n and a[i + 1] == '0' and (b[i + 1] == '0'):
			d += 2
			i += 1
		i += 1
	print(d)


import sys
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def dadd(d, p, val):
	if p in d:
		d[p].append(val)
	else:
		d[p] = [val]

def gi():
	return [xx for xx in input().split()]

def gtc(tc, *ans):
	print('Case #' + str(tc) + ':', *ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def bits(i, n):
	p = bin(i)[2:]
	return (n - len(p)) * '0' + p

def prec(a, pre):
	for i in a:
		pre.append(pre[-1] + i)
	pre.pop(0)

def YN(flag):
	print('YES' if flag else 'NO')

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = fi()
INF = 10 ** 18
uu = t
mod = 10 ** 9 + 7
while t > 0:
	t -= 1
	n = fi()
	a = [ii(), ii()]
	dp = [[-10 ** 18] * 3 for i in range(n + 1)]
	dp[-1][0] = 0
	for i in range(n):
		p = set([int(a[0][i]), int(a[1][i])])
		p = list(p)
		if len(p) == 2:
			dp[i][2] = max(dp[i - 1]) + 2
		elif p[0] == 0:
			if i == 0:
				dp[i][1] = 1
				continue
			dp[i][1] = max(dp[i - 1]) + 1
			dp[i][2] = dp[i - 1][0] + 2
		else:
			if i == 0:
				dp[i][0] = 0
				continue
			dp[i][0] = max(dp[i - 1])
			dp[i][2] = max([dp[i - 1][2], dp[i - 1][0], dp[i - 1][1] + 1])
	print(max(dp[n - 1]))


for j in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	cnt = 0
	i = 0
	while i < n:
		if a[i] != b[i]:
			cnt += 2
		elif a[i] == '1':
			if i < n - 1:
				if a[i + 1] == b[i + 1] == '0':
					cnt += 2
					i += 1
		elif i < n - 1:
			if a[i + 1] == b[i + 1] == '1':
				cnt += 2
				i += 1
			else:
				cnt += 1
		else:
			cnt += 1
		i += 1
	print(cnt)


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


import sys
from math import ceil, floor
from itertools import groupby
ranges = {}
range_char = None
for tc in range(int(input())):
	ranges['0'] = ranges['1'] = 0
	n = int(input())
	table = [list(input()), list(input())]
	cols = []
	prev = None
	for i in range(n):
		c = ''.join(sorted([table[0][i], table[1][i]]))
		if c == '00' and prev == '11' or (prev == '00' and c == '11'):
			del cols[-1]
			cols.append('01')
			prev = '01'
		else:
			cols.append(c)
			prev = c
	d = {x[0]: len(list(x[1])) for x in groupby(sorted(cols))}
	print(d.get('01', 0) * 2 + d.get('00', 0))


def solve(n, s1, s2):
	ans = 0
	i = 0
	while i < n:
		if s1[i] == '0' and s2[i] == '0':
			if i < n - 1:
				if s1[i + 1] == '1' and s2[i + 1] == '1':
					ans += 2
					i += 1
				else:
					ans += 1
			else:
				ans += 1
		elif s1[i] == '1' and s2[i] == '1':
			if i < n - 1:
				if s1[i + 1] == '0' and s2[i + 1] == '0':
					ans += 2
					i += 1
		else:
			ans += 2
		i += 1
	return ans
for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	print(solve(n, s1, s2))


rows = int(input())
for r in range(rows):
	n = int(input())
	s1 = input()
	s2 = input()
	s1 = [int(a) for a in s1]
	s2 = [int(a) for a in s2]
	s12 = list(zip(s1, s2))
	state = 0
	score = 0
	for pair in s12:
		if state == 0:
			if pair == (0, 0):
				state = 1
			elif pair == (1, 1):
				state = 2
			else:
				score += 2
		elif state == 1:
			if pair == (0, 0):
				score += 1
			elif pair == (1, 1):
				state = 0
				score += 2
			else:
				state = 0
				score += 3
		elif pair == (0, 0):
			score += 2
			state = 0
		elif pair != (1, 1):
			score += 2
			state = 0
	if state == 1:
		score += 1
	print(score)


import math
x = int(input())
for i in range(x):
	n = int(input())
	x = input()
	y = input()
	ans = 0
	j = 0
	while j < n:
		if x[j] == '1' and y[j] == '0' or (y[j] == '1' and x[j] == '0'):
			ans += 2
			j += 1
		elif x[j] == '0' and y[j] == '0':
			if j < n - 1 and x[j + 1] == '1' and (y[j + 1] == '1'):
				ans += 2
				j += 2
			else:
				ans += 1
				j += 1
		elif x[j] == '1' and y[j] == '1':
			if j < n - 1 and x[j + 1] == '0' and (y[j + 1] == '0'):
				ans += 2
				j += 2
			else:
				j += 1
	print(ans)


import sys
import os.path
from collections import *
import math
import bisect
import heapq as hq
from fractions import Fraction
from random import randint
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
input = sys.stdin.readline

def solve():
	n = int(input())
	s1 = input().rstrip('\n')
	s2 = input().rstrip('\n')
	x = []
	for i in range(n):
		x.append(s1[i])
		x.append(s2[i])
	for i in range(6):
		x.append('2')
	n *= 2
	res = 0
	i = 0
	while i < n:
		if x[i] == '0' and x[i + 1] == '1' or (x[i] == '1' and x[i + 1] == '0'):
			res += 2
			i += 2
		elif x[i] == '0' and x[i + 1] == '0':
			if x[i + 2] == '1' and x[i + 3] == '1':
				res += 2
				i += 4
			else:
				res += 1
				i += 2
		elif x[i + 2] == '0' and x[i + 3] == '0':
			res += 2
			i += 4
		else:
			res += 0
			i += 2
	print(res)
t = int(input())
while t:
	t -= 1
	solve()


T = int(input())
for _ in range(T):
	n = int(input())
	s1 = str(input())
	s2 = str(input())
	arr = [0 for i in range(n)]
	for i in range(n):
		if s1[i] == s2[i]:
			if s1[i] == '0':
				arr[i] = 1
			else:
				arr[i] = 0
		else:
			arr[i] = 2
	ans = 0
	i = 0
	while i < n:
		if arr[i] == 2:
			ans += 2
		elif arr[i] == 1:
			if i < n - 1:
				if arr[i + 1] == 0:
					ans += 2
					i += 1
				else:
					ans += 1
			else:
				ans += 1
		elif i < n - 1:
			if arr[i + 1] == 1:
				ans += 2
				i += 1
		i += 1
	print(ans)


try:
	T = int(input())
	for i in range(T):
		n = int(input())
		r1 = input()
		r2 = input()
		ans = 0
		c = 'f'
		if r1[0] != r2[0]:
			ans += 2
		elif r1[0] == '0' and r2[0] == '0':
			ans += 1
		for i in range(1, n):
			if r1[i] != r2[i]:
				ans += 2
				c = 'f'
			elif r1[i] == '0' and r2[i] == '0' and (r1[i] == r1[i - 1] or r2[i] == r2[i - 1]):
				ans += 1
				c = 'f'
			elif r1[i] == '1' and r2[i] == '1' and (r1[i] == r1[i - 1] or r2[i] == r2[i - 1]):
				c = 'f'
			elif r1[i] == r2[i] and (r1[i] != r1[i - 1] and r2[i] != r2[i - 1]) and (c == 'f'):
				c = 't'
				if r1[i] == '1' and r2[i] == '1':
					ans += 1
				else:
					ans += 2
			elif r1[i] == r2[i] and (r1[i] != r1[i - 1] and r2[i] != r2[i - 1]) and (c == 't'):
				c = 'f'
				if r1[i] == '0' and r2[i] == '0':
					ans += 1
		print(ans)
except:
	pass


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = [' ' + input(), ' ' + input()]
	dp = [0] * (n + 1)
	last0 = last1 = 0
	for i in range(1, n + 1):
		if ord(s[0][i]) + ord(s[1][i]) == ord('1') + ord('0'):
			dp[i] = dp[i - 1] + 2
			last0 = last1 = i
		elif ord(s[0][i]) + ord(s[1][i]) == ord('1') + ord('1'):
			dp[i] = dp[i - 1]
			if last0:
				dp[i] = max(dp[i], dp[last0 - 1] + 2)
			last1 = i
		else:
			dp[i] = dp[i - 1] + 1
			if last1:
				dp[i] = max(dp[i], dp[last1 - 1] + 2)
			last0 = i
	print(dp[n])


for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	(o, z, res) = (False, False, 0)
	for i in range(n):
		s = a[i] + b[i]
		if s == '01' or s == '10':
			(o, z) = (False, False)
			res += 2
		elif s == '00':
			if o:
				res += 2
				(o, z) = (False, False)
			else:
				z = True
				res += 1
		elif z:
			res += 1
			(o, z) = (False, False)
		else:
			o = True
	print(res)


t = int(input())
for h in range(t):
	n = int(input())
	s1 = input()
	s1 += '2'
	s2 = input()
	s2 += '2'
	r = 0
	ans = True
	for i in range(n):
		if ans:
			if s1[i] == '0' and s2[i] == '1' or (s1[i] == '1' and s2[i] == '0'):
				r += 2
			elif s1[i] == '0' and s2[i] == '0':
				if s1[i + 1] == '1' and s2[i + 1] == '1':
					r += 2
					ans = False
				else:
					r += 1
			elif s1[i] == '1' and s2[i] == '1':
				if s1[i + 1] == '0' and s2[i + 1] == '0':
					r += 2
					ans = False
		else:
			ans = True
	print(r)


for _ in range(int(input())):
	n = int(input())
	a = list(input())
	b = list(input())
	if len(set(a + b)) == 1:
		if '1' in set(a + b):
			print(0)
		else:
			print(n)
	else:
		ans = 0
		diff = set()
		same = set()
		i = 0
		for (first, second) in zip(a, b):
			if first != second:
				diff.add(i)
			else:
				same.add(i)
			i += 1
		i = 0
		for (f, s) in zip(a, b):
			if f == s:
				if i in same and i - 1 in same and (a[i - 1] != a[i]):
					ans += 2
					same.remove(i - 1)
					same.remove(i)
				elif i in same and i + 1 in same and (a[i + 1] != a[i]):
					ans += 2
					same.remove(i + 1)
					same.remove(i)
				elif i in same and a[i] == '1':
					if i - 1 in diff:
						diff.remove(i - 1)
						same.remove(i)
						ans += 2
					elif i + 1 in diff:
						diff.remove(i + 1)
						same.remove(i)
						ans += 2
			i += 1
		ans += 2 * len(diff)
		for i in same:
			if a[i] == '0':
				ans += 1
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	s = []
	for i in range(n):
		if s1[i] == '0' and s2[i] == '0':
			s.append('0')
		elif s1[i] == '1' and s2[i] == '1':
			s.append('1')
		else:
			s.append('2')
	s = ''.join(s)
	i = 0
	total = 0
	while i < len(s) - 1:
		if s[i] == '2':
			total += 2
			i += 1
			continue
		elif s[i] == '0' and s[i + 1] == '1':
			total += 2
			i += 2
		elif s[i] == '1' and s[i + 1] == '0':
			total += 2
			i += 2
		elif s[i] == '1':
			i += 1
		elif s[i] == '0':
			total += 1
			i += 1
	if i == len(s) - 1:
		if s[i] == '2':
			total += 2
		elif s[i] == '0':
			total += 1
	print(total)


for iii in range(int(input())):
	n = int(input())
	s = [list(map(int, list(input()))) for i in range(2)]
	pred_ans = []
	for col in range(n):
		pred_ans.append(s[0][col] + s[1][col])
	ans = 0
	i = 0
	while i < n - 1:
		if set([pred_ans[i], pred_ans[i + 1]]) == set([0, 2]):
			ans += 2
			i += 2
			continue
		elif pred_ans[i] == 0:
			ans += 1
		elif pred_ans[i] == 1:
			ans += 2
		i += 1
	if i == n - 1:
		if pred_ans[-1] == 0:
			ans += 1
		elif pred_ans[-1] == 1:
			ans += 2
	print(ans)


def solve(n, s1, s2):
	l1 = []
	l2 = []
	c = 0
	for i in range(n):
		l1.append(s1[i])
		l2.append(s2[i])
		if len(l1) == 2:
			x = int(l1[0]) + int(l2[0])
			y = int(l1[-1]) + int(l2[-1])
			while len(l1) == 2:
				if x == 1:
					c += 2
					l1.pop(0)
					l2.pop(0)
				elif x + y == 2:
					c += 2
					del l1[:]
					del l2[:]
				elif x == 0:
					c += 1
					l1.pop(0)
					l2.pop(0)
				else:
					l1.pop(0)
					l2.pop(0)
	while len(l1) > 0:
		x = int(l1[0]) + int(l2[0])
		if x == 1:
			c += 2
		elif x == 0:
			c += 1
		l1.pop(0)
		l2.pop(0)
	return c
for i in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	print(solve(n, s1, s2))


def MEX(L):
	S = 0
	if len(L[0]) == 0:
		return 0
	l = []
	for (c1, c2) in zip(L[0], L[1]):
		if c1 != c2:
			l.append(2)
		elif c1 == '0':
			l.append(1)
		else:
			l.append(0)
	prev = l[0]
	S += prev
	for i in range(1, len(l)):
		if l[i] == 1 and prev == 0:
			S += 2
			prev = 2
		elif l[i] == 0 and prev == 1:
			S += 1
			prev = 2
		else:
			S += l[i]
			prev = l[i]
	return S
tests = int(input())
for i in range(tests):
	c = int(input())
	s = input()
	s2 = input()
	L = []
	L.append(s)
	L.append(s2)
	print(MEX(L))


import bisect
import collections
import functools
import heapq
import itertools
import math
import random
import sys
import time
input = sys.stdin.readline

def ri():
	return int(input())

def rf():
	return list(map(float, input().split()))

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

def rs():
	return input().rstrip()

def out_list(x):
	return ' '.join(map(str, x))
MOD = 10 ** 9 + 7
INF = float('inf')

def solve_case():
	n = ri()
	A = [rs() for _ in range(2)]
	res = 0
	for rep in range(2):
		cur = 0
		i = 0
		while i < n:
			if int(A[0][i]) + int(A[1][i]) == 1:
				cur += 2
				i += 1
			elif int(A[0][i]) + int(A[1][i]) == 2:
				if i + 1 < n and int(A[0][i + 1]) + int(A[1][i + 1]) == 0:
					cur += 2
					i += 2
				else:
					i += 1
			elif int(A[0][i]) + int(A[1][i]) == 0:
				if i + 1 < n and int(A[0][i + 1]) + int(A[1][i + 1]) == 2:
					cur += 2
					i += 2
				else:
					cur += 1
					i += 1
		res = max(res, cur)
		for i in range(2):
			A[i] = A[i][::-1]
	print(res)
T = int(input())
for test_case in range(1, T + 1):
	solve_case()


for _ in range(int(input())):
	n = int(input())
	s = input()
	s1 = input()
	ww = []
	for i in range(n):
		w = set([s[i], s1[i]])
		if len(w) == 2:
			ww.append(2)
		elif w.pop() == '0':
			ww.append(1)
		else:
			ww.append(0)
	g_sum = 0
	i = 0
	while i < len(ww):
		if i < len(ww) - 1 and {ww[i], ww[i + 1]} == {0, 1}:
			g_sum += 2
			i += 2
		else:
			g_sum += ww[i]
			i += 1
	print(g_sum)


for _ in range(int(input())):
	n = int(input())
	s = [list(input().strip()) for i in range(2)]
	a = []
	for j in range(n):
		cnt = 0
		for i in range(2):
			cnt += s[i][j] == '1'
			cnt -= s[i][j] == '0'
		a.append(cnt)
	st = []
	for i in range(n):
		if a[i] == -2:
			if st and st[-1] == 2:
				st.pop()
				st.append(0)
			else:
				st.append(a[i])
		elif a[i] == 2:
			if st and st[-1] == -2:
				st.pop()
				st.append(0)
			else:
				st.append(a[i])
		else:
			st.append(0)
	res = 2 * st.count(0) + st.count(-2)
	print(res)


for _ in range(int(input())):
	n = int(input())
	s = [input() for __ in range(2)]
	ans = 0
	i = 0
	while i < n:
		(x, y) = (s[0][i], s[1][i])
		if x != y:
			ans += 2
		elif i + 1 < n:
			i += 1
			(nx, ny) = (s[0][i], s[1][i])
			if x == '0':
				if nx != ny:
					ans += 3
				elif nx == '0':
					ans += 1
					i -= 1
				else:
					ans += 2
			elif nx != ny:
				ans += 2
			elif nx == '1':
				i -= 1
			else:
				ans += 2
		elif x == '0':
			ans += 1
		i += 1
	print(ans)


def solve(a, b):
	s = 0
	w1 = 0
	w0 = 0
	for pair in zip(a, b):
		if pair == ('1', '1'):
			if w0:
				s += 1
				w1 = 0
			else:
				w1 = 1
			w0 = 0
			continue
		if pair == ('0', '0'):
			if w1:
				s += 2
				w0 = 0
			else:
				s += 1
				w0 = 1
			w1 = 0
			continue
		w1 = 0
		w0 = 0
		s += 2
	return s
for _ in '_' * int(input()):
	input()
	print(solve(input(), input()))


for z in range(int(input())):
	n = int(input())
	a = list(input())
	b = list(input())
	i = 0
	sm = 0
	while i < n:
		if a[i] != b[i]:
			sm += 2
		else:
			f = 1
			while i != n - 1 and a[i] == a[i + 1]:
				if a[i] == b[i] and a[i] == '0':
					sm += 1
				i += 1
				if a[i] != b[i]:
					f = 0
					i -= 1
					break
			if f == 1 and i != n - 1:
				if b[i + 1] == a[i + 1]:
					sm += 2
					i += 1
				elif a[i] == '0':
					sm += 1
			elif f == 1 and i == n - 1:
				if a[n - 1] == '0':
					sm += 1
		i += 1
	print(sm)


def solve_case():
	n = int(input())
	a = input()
	b = input()
	ans = 0
	i = 0
	while i < n:
		if a[i] != b[i]:
			ans += 2
			i += 1
		elif i + 1 < n and a[i + 1] == b[i + 1] and (a[i + 1] != a[i]):
			ans += 2
			i += 2
		elif a[i] == '0':
			ans += 1
			i += 1
		else:
			i += 1
	print(ans)
T = int(input())
for t in range(T):
	solve_case()


def solve(n, r1, r2):
	(sol, prev) = (0, None)
	for i in range(n):
		if r1[i] != r2[i]:
			sol += 2
			prev = None
		elif r1[i] == '1':
			if prev == 0:
				sol += 1
				prev = None
			else:
				prev = 1
		elif prev == 1:
			sol += 2
			prev = None
		else:
			sol += 1
			prev = 0
	return sol
t = int(input())
for _ in range(t):
	n = int(input())
	r1 = input()
	r2 = input()
	print(solve(n, r1, r2))


import sys
import math
count = int(sys.stdin.readline())
while count > 0:
	count = count - 1
	len = int(sys.stdin.readline())
	line1 = sys.stdin.readline()
	line2 = sys.stdin.readline()
	sum = 0
	x = 0
	while x < len:
		if line1[x] == '0' and line2[x] == '1':
			sum += 2
			x += 1
			continue
		if line1[x] == '1' and line2[x] == '0':
			sum += 2
			x += 1
			continue
		if line1[x] == '1' and line2[x] == '1' and (line1[x + 1] == '0') and (line2[x + 1] == '0'):
			sum += 2
			x += 2
			continue
		if line1[x] == '0' and line2[x] == '0' and (line1[x + 1] == '1') and (line2[x + 1] == '1'):
			sum += 2
			x += 2
			continue
		if line1[x] == '0' and line2[x] == '0':
			sum += 1
			x += 1
			continue
		x += 1
	print(sum)


t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	total = 0
	flag00 = False
	flag11 = False
	flag10 = False
	for i in range(0, len(s1)):
		s = s1[i] + s2[i]
		if '0' in s and '1' in s:
			flag10 = True
		elif '0' in s:
			if flag00:
				total += 1
			flag00 = True
		else:
			flag11 = True
		total += 2 * flag10 + flag10 * flag00 + 2 * flag00 * flag11
		if flag10:
			flag10 = False
			flag00 = False
			flag11 = False
		if flag11 * flag00:
			flag00 = False
			flag11 = False
	print(total + flag00)


t = int(input())
for case in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	stack = []
	count = 0
	for i in range(n):
		if s1[i] != s2[i]:
			count += 2
			if stack and stack[-1] == '0':
				count += 1
			stack = []
		elif s1[i] == '1':
			if not stack:
				stack.append('1')
				continue
			if stack and stack[-1] == '0':
				count += 2
				stack = []
		else:
			if not stack:
				stack.append('0')
				continue
			if stack and stack[-1] == '1':
				count += 2
				stack = []
				continue
			if stack and stack[-1] == '0':
				count += 1
	if stack and stack[-1] == '0':
		count += 1
	print(count)


from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	s = stdin.readline().strip('\n')
	t = stdin.readline().strip('\n')
	f = i = j = 0
	while i < n - 1:
		if s[i] == '0' and t[i] == '1' or (s[i] == '1' and t[i] == '0'):
			f += 2
		elif s[i] == '1' and t[i] == '1' or (s[i + 1] == '1' and t[i + 1] == '1'):
			li = s[i] + t[i] + t[i + 1] + s[i + 1]
			if li.find('1') != -1 and li.find('0') != -1:
				f += 2
				i += 1
			elif s[i] == '0' and t[i] == '0':
				f += 1
		elif s[i] == '0' and t[i] == '0':
			f += 1
		elif s[i] == '1' and t[i] == '0' or (s[i] == '0' and t[i] == '1'):
			f += 2
		i += 1
	if i == n - 1:
		r = s[-1] + t[-1]
		if r == '00':
			f += 1
		elif r == '10' or r == '01':
			f += 2
	print(f)


from collections import defaultdict, Counter
from math import ceil
test = int(input())
for t in range(test):
	n = int(input())
	s1 = input()
	s2 = input()
	b = [0] * n
	for i in range(n):
		b[i] += int(s1[i]) + int(s2[i])
	j = 0
	ans = 0
	while j < n:
		if b[j] == 1:
			ans += 2
		elif b[j] == 0:
			if j + 1 >= n:
				ans += 1
			elif b[j + 1] in {1, 0}:
				ans += 1
			else:
				ans += 2
				j += 1
		elif j + 1 < n and b[j + 1] == 0:
			ans += 2
			j += 1
		j += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s1 = input().rstrip()
	s2 = input().rstrip()
	s3 = ''.join([str(int(c1) * 2 + int(c2)) for (c1, c2) in zip(s1, s2)])
	ans = 0
	jump = False
	for (c, c_next) in zip(s3, s3[1:] + 'X'):
		if jump:
			jump = False
			continue
		if c in ('1', '2'):
			ans += 2
			continue
		if c_next in ('X', '1', '2') or c == c_next:
			if c == '0':
				ans += 1
			continue
		if c != c_next:
			ans += 2
			jump = True
			continue
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	t = input()
	ans = 0
	seen = -1
	for i in range(n):
		if s[i] != t[i]:
			ans += 2
		else:
			if s[i] == '0':
				ans += 1
			if i != 0 and seen != i - 1 and (s[i - 1] == t[i - 1]) and (s[i] != s[i - 1]):
				ans += 1
				seen = i
	print(ans)


def solve():
	input()
	s1 = input()
	s2 = input()
	cnt = []
	for (ch1, ch2) in zip(s1, s2):
		if ch1 == ch2:
			if ch1 == '0':
				cnt.append(1)
			else:
				cnt.append(0)
		else:
			cnt.append(2)
	result = 0
	cnt2 = []
	current = []
	for i in cnt:
		if i == 2:
			result += 2
			if len(current) > 0:
				cnt2.append(current)
				current = []
		else:
			current.append(i)
	if len(current) > 0:
		cnt2.append(current)
	for cn in cnt2:
		ones = 0
		zeros = False
		for i in cn:
			if i == 1:
				if zeros:
					result += 2
					zeros = False
				else:
					ones += 1
			if i == 0:
				if ones > 0:
					result += ones + 1
					ones = 0
				else:
					zeros = True
		result += ones
	print(result)
t = int(input())
for i in range(t):
	solve()


t = int(input())
for _ in range(t):
	l = int(input())
	r1 = input().strip() + '2'
	r2 = input().strip() + '2'
	p = None
	suma = 0
	for (s1, s2) in zip(r1, r2):
		s = s2 + s1 if s1 == '1' and s2 == '0' else s1 + s2
		if s == '22':
			suma += 1 if p == '00' else 0
			continue
		if s == '01':
			suma += 2 + (1 if p == '00' else 0)
			p = None
			continue
		if s == '00':
			if p == '11':
				suma += 2
				p = None
				continue
			if p == '00':
				suma += 1
				p = '00'
				continue
			p = s
			continue
		if s == '11':
			if p == '00':
				suma += 2
				p = None
				continue
			p = s
			continue
		assert False
	print(suma)


t = input()
t = int(t)
while t > 0:
	n = int(input())
	str1 = input()
	str2 = input()
	list1 = []
	co = 0
	res = 0
	for i in range(n):
		list1.append(str1[i])
		list1.append(str2[i])
		list1 = set(list1)
		if '0' in list1 and '1' in list1:
			lis = [str1[i], str2[i]]
			if co != 0:
				if '0' in lis and '1' in lis:
					res = res + co
				else:
					res = res + (co - 1)
			res = res + 2
			co = 0
			list1 = []
			j = 0
		elif '0' in list1:
			co = co + 1
		list1 = list(list1)
	res = res + co
	print(res)
	t = t - 1


for i in range(int(input())):
	n_cols = int(input())
	(r1, r2) = (input(), input())
	(temp, temp0) = (False, False)
	su = 0
	for j in range(n_cols):
		row = r1[j] + r2[j]
		if row == '11':
			if temp0:
				su += 2
				temp0 = False
				temp = False
			else:
				j += 1
				temp = True
		if row != '11':
			if temp:
				su += 2
				temp = False
			elif row == '00':
				if temp0:
					su += 1
					if j + 1 == n_cols:
						su += 1
				elif j + 1 != n_cols and (r1[j + 1] == '1' and r2[j + 1] == '1'):
					temp0 = True
					j += 1
				else:
					su += 1
			else:
				su += 2
	print(su)


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


import sys, math, bisect
from random import randint
inf = float('inf')
mod = 10 ** 9 + 7

def nCr(n, r):
	return fact(n) / (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def lcm(a, b):
	return int(a / math.gcd(a, b) * b)

def gcd(a, b):
	return int(math.gcd(a, b))

def tobinary(n):
	return bin(n)[2:]

def binarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def lowerBound(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def upperBound(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return -1

def primesInRange(n):
	ans = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def primeFactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n = n // i
	if n > 2:
		factors.append(n)
	return factors

def isPrime(n, k=5):
	if n < 2:
		return True
	for i in range(0, k):
		a = randint(1, n - 1)
		if pow(a, n - 1, n) != 1:
			return False
	return True
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify
import string
for _ in range(int(input())):
	n = int(input())
	arr = input()
	brr = input()
	cnt = 0
	visited = [0] * n
	for i in range(n):
		if visited[i]:
			continue
		curr = [arr[i], brr[i]]
		if '0' in curr and '1' in curr:
			cnt += 2
			visited[i] = 1
		else:
			canUse = True
			if i != n - 1:
				next = [arr[i + 1], brr[i + 1]]
				if '0' in next and '1' in next:
					canUse = False
				elif '0' in curr and '1' in next or ('1' in curr and '0' in next):
					cnt += 2
					visited[i] = 1
					visited[i + 1] = 1
				elif '0' in curr:
					cnt += 1
					visited[i] = 1
				if not canUse and (not visited[i]):
					if '0' in curr:
						cnt += 1
					visited[i] = 1
			elif '0' in curr:
				cnt += 1
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	count = 0
	i = 0
	while i < n:
		if a[i] == '0' and b[i] == '1' or (a[i] == '1' and b[i] == '0'):
			i += 1
			count += 2
		elif i + 1 < n:
			if a[i] == '0' and (a[i + 1] == '1' and b[i + 1] == '1'):
				i += 2
				count += 2
			elif a[i] == '1' and (a[i + 1] == '0' and b[i + 1] == '0'):
				i += 2
				count += 2
			elif a[i] == '0':
				count += 1
				i += 1
			else:
				i += 1
		elif a[i] == '0':
			count += 1
			i += 1
		else:
			i += 1
	print(count)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
import math
from bisect import *
from heapq import *
from collections import defaultdict as dd
from collections import OrderedDict as odict
from collections import Counter as cc
from collections import deque
from itertools import groupby
sys.setrecursionlimit(20 * 20 * 20 * 20 + 10)

def solve():
	n = takein()
	string1 = takesr()
	string2 = takesr()
	ans = 0
	if '0' not in string1 and '0' not in string2:
		ans = 0
	elif '1' not in string1 and '1' not in string2:
		ans = 1
	else:
		ans = 2
	index = 0
	count = 0
	while index < n:
		if string1[index] != string2[index]:
			count += 2
		elif string1[index] == string2[index] == '0':
			if index + 1 < n:
				if string1[index + 1] == string2[index + 1] == '1':
					count += 2
					index += 1
				else:
					count += 1
			else:
				count += 1
		elif index + 1 < n:
			if string1[index + 1] == string2[index + 1] == '0':
				count += 2
				index += 1
		index += 1
	print(max(count, ans))

def main():
	global tt
	if not ONLINE_JUDGE:
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	t = 1
	t = takein()
	for tt in range(1, t + 1):
		solve()
	if not ONLINE_JUDGE:
		print('Time Elapsed :', time.time() - start_time, 'seconds')
		sys.stdout.close()

def takein():
	return int(sys.stdin.readline().rstrip('\r\n'))

def takesr():
	return sys.stdin.readline().rstrip('\r\n')

def takeiar():
	return list(map(int, sys.stdin.readline().rstrip('\r\n').split()))

def takesar():
	return list(map(str, sys.stdin.readline().rstrip('\r\n').split()))

def takeivr():
	return map(int, sys.stdin.readline().rstrip('\r\n').split())

def takesvr():
	return map(str, sys.stdin.readline().rstrip('\r\n').split())

def ispalindrome(s):
	return s == s[::-1]

def invert(bit_s):
	temp = int(bit_s, 2)
	inverse_s = temp ^ 2 ** (len(bit_s) + 1) - 1
	rslt = bin(inverse_s)[3:]
	return str(rslt)

def counter(a):
	q = [0] * max(a)
	for i in range(len(a)):
		q[a[i] - 1] = q[a[i] - 1] + 1
	return q

def counter_elements(a):
	q = dict()
	for i in range(len(a)):
		if a[i] not in q:
			q[a[i]] = 0
		q[a[i]] = q[a[i]] + 1
	return q

def string_counter(a):
	q = [0] * 26
	for i in range(len(a)):
		q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
	return q

def factorial(n, m=1000000007):
	q = 1
	for i in range(n):
		q = q * (i + 1) % m
	return q

def factors(n):
	q = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			q.append(i)
			q.append(n // i)
	return list(sorted(list(set(q))))

def prime_factors(n):
	q = []
	while n % 2 == 0:
		q.append(2)
		n = n // 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			q.append(i)
			n = n // i
	if n > 2:
		q.append(n)
	return list(sorted(q))

def transpose(a):
	(n, m) = (len(a), len(a[0]))
	b = [[0] * n for i in range(m)]
	for i in range(m):
		for j in range(n):
			b[i][j] = a[j][i]
	return b

def power_two(x):
	return x and (not x & x - 1)

def ceil(a, b):
	return -(-a // b)

def seive(n):
	a = [1]
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p = p + 1
	for p in range(2, n + 1):
		if prime[p]:
			a.append(p)
	return a

def pref(li):
	pref_sum = [0]
	for i in li:
		pref_sum.append(pref_sum[-1] + i)
	return pref_sum

def kadane(x):
	sum_so_far = 0
	current_sum = 0
	for i in x:
		current_sum += i
		if current_sum < 0:
			current_sum = 0
		else:
			sum_so_far = max(sum_so_far, current_sum)
	return sum_so_far

def binary_search(li, val):
	ans = -1
	lb = 0
	ub = len(li) - 1
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = mid
			break
	return ans

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


t = int(input())
for i in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	q1 = set()
	total = 0
	flag = -1
	for j in range(n):
		q1.add(int(s1[j]))
		q1.add(int(s2[j]))
		if len(q1) == 2:
			total += 2
			q1.clear()
			if flag == 0:
				total += 1
			flag = -1
		elif flag == 0:
			q1.add(0)
			if len(q1) == 2:
				total += 2
				flag = -1
				q1.clear()
			else:
				total += 1
				q1.clear()
		elif flag == 1:
			q1.add(1)
			if len(q1) == 2:
				total += 2
				flag = -1
				q1.clear()
		else:
			for k in q1:
				if k == 0:
					flag = 0
				else:
					flag = 1
			q1.clear()
	if flag == 0:
		total += 1
	print(total)


cases = int(input())
for _ in range(cases):
	num = int(input())
	s1 = input()
	s2 = input()
	ans = 0
	prev = -1
	for i in range(num):
		cur = s1[i] + s2[i]
		if cur == '01' or cur == '10':
			ans += 2
			if prev == 0:
				ans += 1
			prev = -1
		elif cur == '00':
			if prev == 1:
				ans += 2
				prev = -1
			elif prev == 0:
				ans += 1
			else:
				prev = 0
		elif prev == 0:
			ans += 2
			prev = -1
		else:
			prev = 1
	if prev == 0:
		ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s1 = str(input()) + ' '
	s2 = str(input()) + ' '
	k = 0
	skip = False
	for i in range(n):
		if skip:
			skip = False
			continue
		if s1[i] != s2[i]:
			k += 2
			m = 0
		elif s1[i] == s2[i] == '0':
			if s1[i + 1] == s2[i + 1] == '1':
				k += 2
				skip = True
			else:
				k += 1
		elif s1[i] == s2[i] == '1':
			if s1[i + 1] == s2[i + 1] == '0':
				skip = True
				k += 2
	print(k)


import re
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	x = {'0': '1', '1': '0'}
	c = 0
	i = 0
	while i < n:
		k = a[i]
		p = b[i]
		if k == p:
			if i < n - 1:
				if a[i + 1] == b[i + 1] and a[i + 1] == x[k]:
					c += 2
					i += 2
					continue
				else:
					c += k == '0'
			else:
				c += k == '0'
		else:
			c += 2
		i += 1
	print(c)


n = int(input())
for i in range(0, n):
	o = int(input())
	s = input().rstrip()
	e = input().rstrip()
	x = list(s)
	y = list(e)
	ans = 0
	j = 0
	while j < len(x):
		if x[j] == '0':
			if y[j] == '0':
				if j + 1 < len(x) and x[j + 1] == '1' and (y[j + 1] == '1'):
					ans += 2
					j += 2
				else:
					ans += 1
					j += 1
			else:
				ans += 2
				j += 1
		elif y[j] == '1':
			if j + 1 < len(x) and x[j + 1] == '0' and (y[j + 1] == '0'):
				ans += 2
				j += 2
			else:
				ans += 0
				j += 1
		else:
			ans += 2
			j += 1
	print(ans)


t = int(input())
datos = []
datos2 = []
datos3 = []
i = 0
while i < t:
	n = int(input())
	s1 = input()
	s2 = input()
	datos.append(n)
	datos2.append(s1)
	datos3.append(s2)
	i = i + 1
i = 0
res = []
while i < t:
	aux = []
	j = 0
	while j < datos[i]:
		tep = int(datos2[i][j]) + int(datos3[i][j])
		aux.append(tep)
		j = j + 1
	j = 0
	sum = 0
	while j < datos[i]:
		if aux[j] == 0:
			if j + 1 < datos[i]:
				if aux[j + 1] == 2:
					sum += 2
					j = j + 1
				else:
					sum += 1
			else:
				sum += 1
		elif aux[j] == 1:
			sum += 2
		elif j + 1 < datos[i]:
			if aux[j + 1] == 0:
				sum += 2
				j = j + 1
		j = j + 1
	res.append(sum)
	i = i + 1
i = 0
while i < t:
	print(res[i])
	i = i + 1


import math
import sys
import collections
import bisect
import time
import random
import itertools
import string
from collections import Counter, defaultdict

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

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

def get_string():
	return sys.stdin.readline().strip()
for t in range(int(input())):
	n = int(input())
	s1 = list(get_string())
	s2 = list(get_string())
	ans = 0
	zero = False
	one = False
	pos = 0
	for (i, j) in zip(s1, s2):
		if i != j:
			ans += 2
			if zero == True:
				ans += 1
			zero = False
			one = False
		else:
			if i == '1':
				one = True
			else:
				if zero == True:
					ans += 1
				zero = True
			if one == True and zero == True:
				ans += 2
				one = False
				zero = False
		pos += 1
	if zero == True:
		ans += 1
	print(ans)


def do():
	n = int(input())
	string1 = input()
	string2 = input()
	count_zeroes = 0
	i = 0
	while i < n:
		if string1[i] != string2[i]:
			count_zeroes += 2
		elif string1[i] == '0':
			if i != n - 1 and string1[i + 1] == '1' and (string2[i + 1] == '1'):
				count_zeroes += 2
				i += 1
			else:
				count_zeroes += 1
		elif string1[i] == '1':
			if i != n - 1 and string1[i + 1] == '0' and (string2[i + 1] == '0'):
				count_zeroes += 2
				i += 1
		i += 1
	print(count_zeroes)
t = int(input())
for i in range(t):
	do()


def solve(n, a, b):
	res = 0
	i = 0
	while i < n:
		if a[i] == '1' and b[i] == '0' or (a[i] == '0' and b[i] == '1'):
			res += 2
			i += 1
		elif a[i] == '1' and b[i] == '1':
			if i + 1 < n and a[i + 1] == '0' and (b[i + 1] == '0'):
				res += 2
				i += 2
			else:
				i += 1
				continue
		elif a[i] == '0' and b[i] == '0':
			if i + 1 < n and a[i + 1] == '1' and (b[i + 1] == '1'):
				res += 2
				i += 2
			else:
				res += 1
				i += 1
	return res
t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	ans = solve(n, a, b)
	print(ans)


def solve(s1, s2):
	r = 0
	index = 0
	ZERO_ONE = ('0', '1')
	ONE_ZERO = ('1', '0')
	ONE_ONE = ('1', '1')
	ZERO_ZERO = ('0', '0')
	while index < len(s1):
		current = (s1[index], s2[index])
		if current == ZERO_ONE or current == ONE_ZERO:
			r += 2
			index += 1
			continue
		if current == ONE_ONE:
			if index == len(s1) - 1:
				index += 1
				continue
			next_pair = (s1[index + 1], s2[index + 1])
			if next_pair == ZERO_ZERO:
				r += 2
				index += 2
				continue
			index += 1
			continue
		if index == len(s1) - 1:
			r += 1
			index += 1
			continue
		next_pair = (s1[index + 1], s2[index + 1])
		if next_pair == ONE_ONE:
			r += 2
			index += 2
			continue
		r += 1
		index += 1
	return r

def main():
	t = int(input())
	for _ in range(t):
		a = input()
		a = input()
		b = input()
		print(solve(a, b))
main()


def max_mex(arr):
	ptr = 0
	tot = 0
	while ptr < len(arr[0]):
		if arr[0][ptr] != arr[1][ptr]:
			tot += 2
			ptr += 1
		elif arr[0][ptr] == '1' and ptr + 1 < len(arr[0]):
			if arr[0][ptr + 1] != arr[1][ptr + 1]:
				ptr += 1
			elif arr[0][ptr + 1] == '1':
				ptr += 1
			else:
				tot += 2
				ptr += 2
		elif arr[0][ptr] == '0' and ptr + 1 < len(arr[0]):
			if arr[0][ptr + 1] != arr[1][ptr + 1]:
				tot += 1
				ptr += 1
			elif arr[0][ptr + 1] == '1':
				ptr += 2
				tot += 2
			else:
				tot += 1
				ptr += 1
		else:
			tot += 1 if arr[0][ptr] == '0' else 0
			ptr += 1
	return tot
t = input()
for _ in range(int(t)):
	length = input()
	row_1 = input()
	row_2 = input()
	arr = [row_1, row_2]
	print(max_mex(arr))


from sys import stdin
t = int(stdin.readline())
for _ in range(t):
	r = int(stdin.readline())
	n = stdin.readline().strip('\n')
	m = stdin.readline().strip('\n')
	mex = 0
	counter = 0
	for i in range(len(n)):
		if n[i] == '0' and m[i] == '0':
			if counter == -1:
				mex += 2
				counter = 0
			else:
				counter = 1
				mex += 1
		elif n[i] == '1' and m[i] == '1':
			if counter == 1:
				mex += 1
				counter = 0
			else:
				counter = -1
		else:
			counter = 0
			mex += 2
	print(mex)


import math as m
for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	dp = [0] * n
	a = [0] * n
	ans = 0
	for i in range(n):
		a[i] = int(s1[i]) + int(s2[i])
	for i in range(n):
		if a[i] == 1:
			ans += 2
		if a[i] == 0:
			ans += 1
		if a[i] == 2:
			if i != 0:
				if a[i - 1] == 0 and dp[i - 1] == 0:
					dp[i - 1] = 1
					ans += 1
					continue
			if i != n - 1:
				if a[i + 1] == 0 and dp[i + 1] == 0:
					dp[i + 1] = 1
					ans += 1
					continue
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	mex = i = 0
	while i < n:
		if s1[i] != s2[i]:
			mex += 2
			i += 1
		else:
			flag = True
			for j in range(i + 1, n):
				if s1[i] == '0':
					if s1[j] != s2[j]:
						mex += 3
						i = j + 1
					elif s1[j] == s2[j] == '0':
						mex += 1
						i = j
					elif s1[j] == s2[j] == '1':
						mex += 2
						i = j + 1
					flag = False
					break
				elif s1[j] != s1[i] or s2[j] != s1[i]:
					mex += 2
					i = j + 1
					flag = False
					break
			if flag:
				if s1[i] == '0':
					mex += n - i
				i = n
	print(mex)


for _ in range(int(input())):
	sdf = input()
	a = input()
	b = input()
	i = 0
	ans = 0
	mark = []
	while i < len(a):
		if a[i] != b[i]:
			ans += 2
			i += 1
		elif a[i] == '0':
			if i + 1 < len(a) and a[i + 1] == b[i + 1] and (a[i + 1] == '1'):
				ans += 2
				i += 2
			else:
				i += 1
				ans += 1
		elif i + 1 < len(a) and a[i + 1] == b[i + 1] and (a[i + 1] == '0'):
			ans += 2
			i += 2
		else:
			i += 1
			ans += 0
	print(ans)


def MEX(a, b):
	(a, b) = min(a, b)
	if a == 0 and b == 0:
		return 0
	if a == 0 and b == 1:
		return 2
	if a == 1 and b == 1:
		return 0

def solve():
	n = int(input())
	a = input()
	b = input()
	ans = 0
	cur = 0
	mex = None
	while cur < n:
		(x, y) = (a[cur], b[cur])
		(intX, intY) = (int(x), int(y))
		if intX + intY == 1:
			ans += 2
			cur += 1
			continue
		if intX + intY == 2:
			cur += 1
			if cur == n:
				break
			while cur < n and a[cur] != '0' and (b[cur] != '0'):
				cur += 1
			if cur == n:
				break
			ans += 2
			cur += 1
		else:
			if cur + 1 == n:
				ans += 1
				break
			if a[cur + 1] == '1' and b[cur + 1] == '1':
				ans += 2
				cur += 2
			else:
				ans += 1
				cur += 1
	print(ans)
t = int(input())
while t:
	t -= 1
	solve()


from sys import stdin
t = int(input())
for _ in range(t):
	n = int(input())
	s1 = stdin.readline().strip()
	s2 = stdin.readline().strip()
	ans = 0
	i = 0
	while i < n:
		if s1[i] == '0' and s2[i] == '0':
			if i < n - 1:
				if s1[i + 1] == '1' and s2[i + 1] == '1':
					ans += 2
					i += 2
				else:
					ans += 1
					i += 1
			else:
				ans += 1
				i += 1
		elif s1[i] == '1' and s2[i] == '1':
			if i < n - 1:
				if s1[i + 1] == '0' and s2[i + 1] == '0':
					ans += 2
					i += 2
				else:
					i += 1
			else:
				i += 1
		else:
			ans += 2
			i += 1
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	st = input()
	st1 = input()
	ar = []
	for i in range(n):
		if int(st[i]) ^ int(st1[i]) == 1:
			ar.append(2)
		if st[i] == st1[i] == '1':
			ar.append(0)
		if st[i] == st1[i] == '0':
			ar.append(1)
	ans = 0
	two = 0
	lp = False
	pre = ar[0]
	cnt = 0
	for i in ar:
		if lp:
			pre = i
		if i == 2:
			if lp:
				ans += 2
				pre = 2
			else:
				ans += pre * cnt
				ans += 2
				pre = 2
				lp = True
			cnt = 0
		elif pre == 1 and i == 0:
			lp = True
			ans += 2
			ans += cnt - 1
			cnt = 0
		elif pre == 0 and i == 1:
			lp = True
			ans += 2
			cnt = 0
		elif pre == 1 and i == 1:
			lp = False
			cnt += 1
		else:
			lp = False
			cnt = 0
	if pre != 2:
		ans += pre * cnt
	print(ans)


import sys
input = sys.stdin.readline

def s(a):
	n = len(a)
	r = 0
	for i in range(n):
		if a[i] == 0:
			if i > 0 and a[i - 1] == 1:
				r += 2
			elif i + 1 < n and a[i + 1] == 1:
				r += 2
				a[i + 1] = 2
			else:
				r += 1
	return r

def solve():
	n = int(input())
	a = input()
	b = input()
	c = [0] * n
	for i in range(n):
		if a[i] != b[i]:
			c[i] = 2
		elif a[i] == '1':
			c[i] = 1
	a = []
	r = 0
	for i in c:
		if i == 2:
			r += s(a) + 2
			a = []
		else:
			a.append(i)
	r += s(a)
	print(r)
for i in range(int(input())):
	solve()


from sys import stdin, stdout

def INPUT():
	return list((int(i) for i in stdin.readline().split()))

def inp():
	return stdin.readline()

def out(x):
	return stdout.write(x)
from math import *
from decimal import *
INT_MAX = 10 ** 13
mod = 998244353

def ceil(a, b):
	return (a + b - 1) // b

def pow(a, n):
	res = 1
	while n:
		if n & 1:
			res = res * a % mod
		a = a * a
		a %= mod
		n >>= 1
	return res
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	n = len(a)
	paired = [False] * (n + 1)
	ans = 0
	for i in range(n):
		if int(a[i]) ^ int(b[i]) == 1:
			ans += 2
		elif i == 0:
			if a[i] == '0' and b[i] == '0':
				ans += 1
		elif a[i] == '0' and b[i] == '0':
			if a[i - 1] == '1' and b[i - 1] == '1' and (paired[i - 1] == False):
				ans += 2
				paired[i] = True
			else:
				ans += 1
		elif a[i - 1] == '0' and b[i - 1] == '0' and (paired[i - 1] == False):
			ans += 1
			paired[i] = True
	print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()

def solve():
	N = int(input())
	S = input()
	T = input()
	ans = 0
	i = 0
	while i < N:
		if S[i] != T[i]:
			ans += 2
		elif S[i] == '0':
			if i + 1 < N:
				if S[i + 1] == '1' and T[i + 1] == '1':
					ans += 2
					i += 1
				else:
					ans += 1
			else:
				ans += 1
		elif i + 1 < N and S[i + 1] == T[i + 1] == '0':
			ans += 2
			i += 1
		i += 1
	print(ans)
	return
T = int(input())
for i in range(1, T + 1):
	solve()


import sys
inp = sys.stdin.readline()
test = int(inp.strip('\n'))
result = ''
for i in range(test):
	inp = sys.stdin.readline()
	size = int(inp.strip('\n'))
	inp = sys.stdin.readline()
	string1 = inp.strip('\n')
	inp = sys.stdin.readline()
	string2 = inp.strip('\n')
	cost = i = 0
	while i < size:
		if string1[i] == '0':
			if string2[i] == '0':
				if i + 1 < size:
					if string1[i + 1] == '1' and string2[i + 1] == '1':
						cost += 2
						i += 1
					else:
						cost += 1
				else:
					cost += 1
			else:
				cost += 2
		elif string2[i] == '0':
			cost += 2
		elif i + 1 < size:
			if string1[i + 1] == '0' and string2[i + 1] == '0':
				cost += 2
				i += 1
			else:
				cost += 0
		else:
			cost += 0
		i += 1
	sys.stdout.write(str(cost) + '\n')


a = int(input())
for i in range(a):
	n = int(input())
	tab1 = input()
	tab2 = input()
	tab = ''
	for j in range(n):
		if tab1[j] == '0' and tab2[j] == '0':
			tab += '1'
		elif tab1[j] == '1' and tab2[j] == '1':
			tab += '0'
		else:
			tab += '2'
	tab += '3'
	cnt = 0
	i = 0
	while i < n:
		if tab[i] == '0' and tab[i + 1] == '1' or (tab[i] == '1' and tab[i + 1] == '0'):
			cnt += 2
			i += 1
		else:
			cnt += int(tab[i])
		i += 1
	print(cnt)


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
from bisect import bisect_left as lower_bound, bisect_right as upper_bound

def so():
	return int(input())

def st():
	return input()

def mj():
	return map(int, input().strip().split(' '))

def msj():
	return map(str, input().strip().split(' '))

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

def lebe():
	return list(map(int, input()))

def dmain():
	sys.setrecursionlimit(1000000)
	threading.stack_size(1024000)
	thread = threading.Thread(target=main)
	thread.start()

def joro(L):
	return ''.join(map(str, L))

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

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def npr(n, r):
	return factorial(n) // factorial(n - r) if n >= r else 0

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def tir(a, b, c):
	if 0 == c:
		return 1
	if len(a) <= b:
		return 0
	if c != -1:
		return tir(a, 1 + b, c + a[b]) or tir(a, b + 1, c - a[b]) or tir(a, 1 + b, c)
	else:
		return tir(a, 1 + b, a[b]) or tir(a, b + 1, -a[b]) or tir(a, 1 + b, -1)

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val, lb, ub):
	ans = -1
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = mid
			break
	return ans

def kadane(x):
	sum_so_far = 0
	current_sum = 0
	for i in x:
		current_sum += i
		if current_sum < 0:
			current_sum = 0
		else:
			sum_so_far = max(sum_so_far, current_sum)
	return sum_so_far

def pref(li):
	pref_sum = [0]
	for i in li:
		pref_sum.append(pref_sum[-1] + i)
	return pref_sum

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	li = []
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, len(prime)):
		if prime[p]:
			li.append(p)
	return li

def primefactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n //= i
	if n > 2:
		factors.append(n)
	return factors

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def tr(n):
	return n * (n + 1) // 2

def ti(x):
	import math
	if x >= 0:
		s = math.sqrt(x)
	if s * s == x:
		return 1
	return 0
boi = 998244353

def ryu(a, b):
	re = 1
	while b != 0:
		if b % 2 != 0:
			re *= a
			re %= boi
		b = b // 2
		a *= a
		a %= boi
	return re
fa = [0] * 100007

def pow(x, y, p):
	re = 1
	x = x % p
	while y > 0:
		if y % 2 != 0:
			re = re * x % p
		y = y // 2
		x = x * x % p
	return re

def mi(n, p):
	return pow(n, p - 2, p)

def ncr(n, r, p):
	if n < r:
		return 0
	if r == 0:
		return 1
	return fa[n] * mi(fa[r], p) % p * mi(fa[n - r], p) % p % p

def iu():
	import re
	import sys
	input = sys.stdin.readline
	import math as my
	m = so()
	s = st()
	ss = st()
	su = 0
	te = ''
	for i in range(m):
		s1 = ''
		s1 += s[i]
		s1 += ss[i]
		if s1 == '01' or s1 == '10':
			su += 2
			te = s1
		elif s1 == '11':
			if te == '00':
				su += 1
				te = '22'
			else:
				te = s1
		elif te == '11':
			su += 2
			te = '22'
		else:
			su += 1
			te = s1
	print(su)

def main():
	for i in range(so()):
		iu()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	c = 0
	skip = False
	done = False
	for i in range(n - 1):
		if skip:
			skip = False
			continue
		if s1[i] != s2[i]:
			c += 2
		elif s1[i + 1] != s1[i] and s2[i + 1] != s1[i]:
			c += 2
			if i == n - 2:
				done = True
				break
			skip = True
		elif s1[i] == '0':
			c += 1
	if not done:
		if s1[n - 1] != s2[n - 1]:
			c += 2
		elif s1[n - 1] == '0':
			c += 1
	print(c)


def main():
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
	inf = 1e+17
	mod = 10 ** 9 + 7

	def factorial(n):
		f = 1
		for i in range(1, n + 1):
			f = f * i % mod
		return f

	def ncr(n, r):
		num = den = 1
		for i in range(r):
			num = num * (n - i) % mod
			den = den * (i + 1) % mod
		return num * pow(den, mod - 2, mod) % mod

	def mex(a, b):
		if a == '0' and b == '0':
			return 1
		elif a == '1' and b == '1':
			return 0
		else:
			return 2

	def solve(s1, s2):
		last_mex = mex(s1[0], s2[0])
		Sum = mex(s1[0], s2[0])
		for i in range(1, n):
			if last_mex == 0 and mex(s1[i], s2[i]) == 1:
				Sum += 2
				last_mex = 2
			elif last_mex == 1 and mex(s1[i], s2[i]) == 0:
				Sum += 1
				last_mex = 2
			else:
				Sum += mex(s1[i], s2[i])
				last_mex = mex(s1[i], s2[i])
		return Sum
	t = int(input())
	ans = []
	for _ in range(t):
		n = int(input())
		s1 = input()[:-1]
		s2 = input()[:-1]
		ans.append(solve(s1, s2))
	p = 1
	for answer in ans:
		print(answer)
		p += 1
import sys, threading
import bisect
import math
import itertools
from sys import stdout
import heapq
from queue import PriorityQueue
input = sys.stdin.readline
thread = threading.Thread(target=main)
thread.start()
thread.join()


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s2 = input()
	cnt = 0
	prev = -1
	for i in range(n):
		if s[i] == '1' and s2[i] == '1':
			if prev == 0:
				cnt += 1
				prev = -1
			else:
				prev = 1
		elif s[i] == '0' and s2[i] == '0':
			if prev == 1:
				cnt += 2
				prev = -1
			else:
				cnt += 1
				prev = 0
		else:
			cnt += 2
			prev = -1
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	a = i = 0
	while i < n:
		if s1[i] + s2[i] == '10' or s1[i] + s2[i] == '01':
			a = a + 2
			i = i + 1
		elif s1[i] + s2[i] == '00':
			if i != n - 1 and s1[i + 1] + s2[i + 1] == '11':
				a = a + 2
				i = i + 2
			else:
				a = a + 1
				i = i + 1
		elif i != n - 1 and s1[i + 1] + s2[i + 1] == '00':
			a = a + 2
			i = i + 2
		else:
			a = a
			i = i + 1
	print(a)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = input().strip()
	b = input().strip()
	i = 0
	ans = 0
	last = -1
	if n == 1:
		if a[-1] == '0' and b[-1] == '0':
			print(1)
			continue
		elif a[-1] == '1' and b[-1] == '1':
			print(0)
			continue
		else:
			print(2)
			continue
	while i < n - 1:
		if a[i] == '1' and a[i + 1] == '0' and (b[i] == '1') and (b[i + 1] == '0'):
			ans += 2
			last = i
			i += 2
			continue
		if a[i] == '0' and a[i + 1] == '1' and (b[i] == '0') and (b[i + 1] == '1'):
			ans += 2
			last = i
			i += 2
			continue
		if a[i] == '0' and b[i] == '0':
			ans += 1
		elif a[i] == '1' and b[i] == '1':
			ans += 0
		else:
			ans += 2
		i += 1
	if last != n - 2:
		if a[-1] == '0' and b[-1] == '0':
			ans += 1
		elif a[-1] == '1' and b[-1] == '1':
			ans += 0
		else:
			ans += 2
	print(ans)


for _ in range(int(input())):
	ans = 0
	input()
	prev = '2'
	for (c, d) in zip(input(), input()):
		if c != d:
			ans += 2
			prev = '2'
		else:
			if c == '0':
				ans += 1
			if c != prev != '2':
				ans += 1
				prev = '2'
			else:
				prev = c
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	first = input()
	second = input()
	mex = 0
	is_pair_pass = 0
	for i in range(n):
		if is_pair_pass == 1:
			is_pair_pass = 0
			continue
		if first[i] != second[i]:
			mex = mex + 2
		elif i + 1 < n and (first[i + 1] != first[i] and second[i + 1] != second[i]):
			is_pair_pass = 1
			mex = mex + 2
		else:
			mex = mex + 1 - int(first[i])
	print(mex)


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


t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input()
	l1 = [int(i) for i in s1]
	s2 = input()
	l2 = [int(i) for i in s2]
	c = 0
	q = -1
	r = 0
	for i in range(n):
		if l1[i] != l2[i]:
			if q == 0:
				q = -1
				c += 1
				r = 0
			q = -1
			c += 2
		elif l1[i] == l2[i] and l1[i] == 1:
			if q == 0:
				q = -1
				c += 2
				r = 0
			else:
				q = 1
		elif l1[i] == l2[i] and l1[i] == 0:
			if q == 1:
				q = -1
				c += 2
			elif q == 0:
				c += 1
				r = 1
			else:
				q = 0
				r = 1
	print(c + r)


def solve():
	n = int(input())
	ar = list(map(int, input()))
	br = list(map(int, input()))
	count = 0
	i = 0
	while i < n:
		if ar[i] != br[i]:
			count += 2
			i += 1
		elif ar[i] == br[i] and i < n - 1 and (ar[i + 1] == br[i + 1]) and (ar[i] != ar[i + 1]):
			count += 2
			i += 2
		elif ar[i] == br[i] == 1:
			count += 0
			i += 1
		elif ar[i] == br[i] == 0:
			count += 1
			i += 1
	return count
for t in range(0, int(input())):
	print(solve())


def solve(s1, s2):
	n = len(s1)
	assert len(s2) == n
	last = None
	res = 0
	for i in range(n):
		col = {s1[i], s2[i]}
		if len(col) == 2:
			res += 2
			last = None
		elif '0' in col:
			if last == 1:
				res += 2
				last = None
			else:
				res += 1
				last = 0
		elif last == 0:
			res += 1
			last = None
		else:
			last = 1
	return res
t = int(input())
for _ in range(t):
	input()
	s1 = input().strip()
	s2 = input().strip()
	print(solve(s1, s2))


tests = int(input())
for i in range(0, tests):
	allzero = False
	allones = False
	used = False
	lenTuple = int(input())
	fst = input()
	snd = input()
	fst = list(map(int, fst))
	snd = list(map(int, snd))
	tuples = list(zip(fst, snd))
	sum = 0
	for j in range(0, lenTuple):
		used = False
		prev = tuples[j]
		if prev[0] == 0 and prev[1] == 1 or (prev[0] == 1 and prev[1] == 0):
			sum += 2
			if allzero:
				sum += 1
			allzero = False
			allones = False
		if allzero:
			if prev[0] == 1 or prev[1] == 1:
				sum += 2
				allzero = False
				used = True
			if prev[0] == 0 and prev[1] == 0:
				sum += 1
		if allones:
			if prev[0] == 0 or prev[1] == 0:
				sum += 2
				allones = False
				used = True
		if not used:
			if prev[0] == 0 and prev[1] == 0:
				allzero = True
			if prev[0] == 1 and prev[1] == 1:
				allones = True
	if allzero:
		sum += 1
	print(sum)


for x in range(int(input())):
	N = int(input())
	s = input()
	t = input()
	ans = 0
	seen = -1
	for x in range(N):
		if s[x] != t[x]:
			ans += 2
		else:
			if s[x] == '0':
				ans += 1
			if s[x - 1] == t[x - 1] and s[x] != s[x - 1] and (x != 0) and (seen != x - 1):
				ans += 1
				seen = x
	print(ans)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
from random import randint as ri
mod = int(1000000000.0) + 7
mod = 998244353
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = ip()
for _ in range(t):
	n = ip()
	a = ips()
	b = ips()
	dic = set()
	ans = 0
	for i in range(n):
		cur = set()
		cur.add(a[i])
		cur.add(b[i])
		if len(dic) == 0:
			if len(cur) == 2:
				ans += 2
				dic = set()
			else:
				dic = set(list(dic) + list(cur))
		elif len(cur) == 2:
			ans += 2
			if '0' in dic:
				ans += 1
			dic = set()
		elif '0' in cur and '0' in dic:
			ans += 1
		elif '0' in cur and '1' in dic:
			ans += 2
			dic = set()
		elif '1' in cur and '0' in dic:
			ans += 2
			dic = set()
		else:
			pass
	if len(dic) != 0:
		if '0' in dic:
			ans += 1
	print(ans)


def solve():
	sum = 0
	l = int(input())
	(a, b) = (input(), input())
	i = 0
	while i < l:
		if i < l - 1 and a[i] == '0' and (a[i + 1] == '1') and (b[i] == '0') and (b[i + 1] == '1') or (i < l - 1 and a[i] == '1' and (a[i + 1] == '0') and (b[i] == '1') and (b[i + 1] == '0')):
			sum += 2
			i += 1
		elif a[i] == '0' and b[i] == '1' or (a[i] == '1' and b[i] == '0'):
			sum += 2
		elif a[i] == '0' and b[i] == '0':
			sum += 1
		elif a[i] == '1' and b[i] == '1':
			sum += 0
		i += 1
	print(sum)
T = int(input())
for i in range(1, T + 1):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	st1 = input()
	st2 = input()
	r = 0
	j = 0
	while j < n:
		if st1[j] == '1' and st2[j] == '0':
			r += 2
		elif st1[j] == '0' and st2[j] == '1':
			r += 2
		elif j < n - 1:
			if st1[j] == '1' and st2[j] == '1' and (st1[j + 1] == '0') and (st2[j + 1] == '0'):
				j += 2
				r += 2
				continue
			elif st1[j] == '0' and st2[j] == '0' and (st1[j + 1] == '1') and (st2[j + 1] == '1'):
				j += 2
				r += 2
				continue
			elif st1[j] == '0' and st2[j] == '0':
				r += 1
				j += 1
				continue
			elif st1[j] == '1' and st2[j] == '1':
				j += 1
				continue
		elif st1[j] == '0' and st2[j] == '0':
			r += 1
			j += 1
			continue
		elif st1[j] == '1' and st2[j] == '1':
			j += 1
			continue
		j += 1
	print(r)


for _ in range(int(input())):
	n = int(input())
	string1 = input()
	string2 = input()
	ans = 0
	if '0' not in string1 and '0' not in string2:
		ans = 0
	elif '1' not in string1 and '1' not in string2:
		ans = 1
	else:
		ans = 2
	i = 0
	c = 0
	while i < n:
		if string1[i] != string2[i]:
			c += 2
		elif string1[i] == string2[i] == '0':
			if i + 1 < n:
				if string1[i + 1] == string2[i + 1] == '1':
					c += 2
					i += 1
				else:
					c += 1
			else:
				c += 1
		elif i + 1 < n:
			if string1[i + 1] != string2[i + 1] or string1[i + 1] == string2[i + 1] == '0':
				c += 2
				i += 1
		i += 1
	print(max(c, ans))


l = int(input())
for _ in range(l):
	ll = int(input())
	s1 = input()
	bin1 = [int(i) for i in s1]
	s2 = input()
	bin2 = [int(i) for i in s2]
	total = 0
	n = 0
	while n < ll:
		if bin1[n] != bin2[n]:
			total += 2
		elif bin1[n] == bin2[n] and int(bin2[n]) == 1:
			if n + 1 < ll and (bin1[n + 1] == 0 or bin2[n + 1] == 0):
				total += 2
				n += 1
		elif n + 1 < ll:
			n += 1
			if bin1[n] == 1 and bin2[n] == 1:
				total += 2
			else:
				total += 1
				n -= 1
		else:
			total += 1
		n += 1
	print(total)


import sys
from functools import lru_cache
input = sys.stdin.readline

def cin_int():
	return int(input())

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

def cin_ls():
	return input().split()

def main():
	v = {(True, True): 2, (True, False): 1, (False, True): 0, (False, False): 0}

	@lru_cache(None)
	def dp(idx, _01):
		if idx == len(s1):
			return v[_01]
		(a, b) = (int(s1[idx]), int(s2[idx]))
		l = list(_01)
		l[a] = True
		l[b] = True
		return max(dp(idx + 1, tuple(l)), dp(idx + 1, (False, False)) + v[tuple(l)])

	def sv():
		idx = 0
		ans = 0
		pre = [False, False]
		while idx != len(s1):
			(a, b) = (int(s1[idx]), int(s2[idx]))
			if a + b == 2:
				if pre[0]:
					pre = [False, False]
					ans += 2
				else:
					pre[1] = True
			elif a + b == 1:
				ans += v[tuple(pre)]
				pre = [False, False]
				ans += 2
			elif pre[1]:
				pre = [False, False]
				ans += 2
			elif pre[0]:
				ans += 1
			else:
				pre[0] = True
			idx += 1
		return ans + v[tuple(pre)]
	for _ in range(cin_int()):
		input()
		s1 = str(input()).strip('\n').strip()
		s2 = str(input()).strip('\n').strip()
		print(sv())
main()


import os
import sys
from io import BytesIO, IOBase
import math
from queue import Queue
import collections
import itertools
import bisect
import heapq
import random

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def primeFactors(n):
	cnt = []
	while n % 2 == 0:
		cnt.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			cnt.append(i)
			n = n / i
	if n > 2:
		cnt.append(int(n))
	return cnt

def primeFactorsCount(n):
	cnt = 0
	while n % 2 == 0:
		cnt += 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			cnt += 1
			n = n // i
	if n > 2:
		cnt += 1
	return cnt

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)

def countcon(s, i):
	c = 0
	ch = s[i]
	for i in range(i, len(s)):
		if s[i] == ch:
			c += 1
		else:
			break
	return c

def lis(arr):
	n = len(arr)
	lis = [1] * n
	for i in range(1, n):
		for j in range(0, i):
			if arr[i] > arr[j] and lis[i] < lis[j] + 1:
				lis[i] = lis[j] + 1
	maximum = 0
	for i in range(n):
		maximum = max(maximum, lis[i])
	return maximum

def isSubSequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def maxfac(n):
	root = int(n ** 0.5)
	for i in range(2, root + 1):
		if n % i == 0:
			return n // i
	return n

def p2(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def seive(n):
	primes = [True] * (n + 1)
	primes[1] = primes[0] = False
	i = 2
	while i * i <= n:
		if primes[i] == True:
			for j in range(i * i, n + 1, i):
				primes[j] = False
		i += 1
	pr = []
	for i in range(0, n + 1):
		if primes[i]:
			pr.append(i)
	return pr

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def denofactinverse(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return pow(fac, m - 2, m)

def numofact(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return fac

def sod(n):
	s = 0
	while n > 0:
		s += n % 10
		n //= 10
	return s

def inv(n, m):
	return pow(n, m - 2, m)

def countcon2(s1, s2, i):
	n = len(s1)
	cnt = 0
	while i < n and s1[i] == s2[i]:
		i += 1
		cnt += 1
	return cnt
for xyz in range(0, int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	ans = 0
	p = '2'
	for i in range(0, n):
		if s1[i] != s2[i]:
			ans += 2
			p = '2'
		elif s1[i] == '0':
			ans += 1
			if p == '1':
				ans += 1
				p = '2'
			else:
				p = '0'
		elif p == '0':
			ans += 1
			p = '2'
		else:
			p = '1'
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	c = 0
	y = 0
	y0 = 0
	y1 = 0
	for i in range(n):
		if s1[i] == '1' and s2[i] == '0' or (s1[i] == '0' and s2[i] == '1'):
			if y0 == 1:
				c += 2
				y0 = 0
				y1 = 0
			else:
				c += 2
				y0 = 0
				y1 = 0
		elif s1[i] == '1' and s2[i] == '1':
			if y0 == 1:
				c += 1
				y0 = 0
				y1 = 0
			else:
				y1 = 1
		elif y1 == 1:
			c += 2
			y0 = 0
			y1 = 0
		else:
			y0 = 1
			c += 1
	print(c)


test = int(input())
for _ in range(test):
	length = int(input())
	(s1, s2) = (input(), input())
	(found, result, ones) = ([0, 0], 0, 0)
	for i in range(length):
		if s1[i] == '0' and s2[i] == '0':
			if found[1] == 1:
				result += 2
				found = [0, 0]
			else:
				if ones == 0:
					ones = 1
				else:
					result += 1
				found[0] = 1
		if s1[i] == '1' and s2[i] == '1':
			if found[0] == 1:
				result += 2
				found = [0, 0]
				ones = 0
			else:
				found[1] = 1
		if s1[i] == '1' and s2[i] == '0' or (s1[i] == '0' and s2[i] == '1'):
			result = result + 2 + ones
			found = [0, 0]
			ones = 0
	print(result + ones)


z = int(input())
for _ in range(z):
	n = int(input())
	x = input()
	y = input()
	c = 0
	i = 0
	while i < n:
		if x[i] == '0' and y[i] == '1' or (y[i] == '0' and x[i] == '1'):
			c += 2
		elif x[i] == '0' and y[i] == '0':
			if i < n - 1 and (x[i + 1] == '1' and y[i + 1] == '1'):
				c += 2
				i += 1
			else:
				c += 1
		elif i < n and (x[i] == '1' and y[i] == '1'):
			if i < n - 1 and (x[i + 1] == '0' and y[i + 1] == '0'):
				c += 2
				i += 1
			else:
				c += 0
		else:
			c += 1
		i += 1
	print(c)


import sys
import math
from bisect import bisect_right as br

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

def str_arr():
	return list(map(str, sys.stdin.readline().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	ans = 0
	dict0 = {}
	dict1 = {}
	for i in range(n):
		if a[i] == '0' and b[i] == '0':
			dict0[i] = True
		elif a[i] == '1' and b[i] == '1':
			dict1[i] = True
		else:
			ans += 2
	for i in dict0.keys():
		if dict1.get(i - 1) == True:
			ans += 2
		elif dict1.get(i + 1) == True:
			dict1[i + 1] = 0
			ans += 2
		else:
			ans += 1
	print(ans)


T = int(input())
while T > 0:
	T -= 1
	n = int(input())
	s1 = input()
	s2 = input()
	ans = 0
	_11 = _00 = 0
	for i in range(n):
		if s1[i] != s2[i]:
			ans += 2
			if _00 == 1:
				ans += 1
			_11 = _00 = 0
		elif s1[i] == '0':
			if _11 == 1:
				ans += 2
				_11 = _00 = 0
			elif _00 == 1:
				ans += 1
				_11 = 0
				_00 = 1
			else:
				_11 = 0
				_00 = 1
		else:
			if _00 == 1:
				ans += 2
				_11 = _00 = 0
			else:
				_11 = 1
				_00 = 0
			pass
	print(ans + _00)


def main():
	n = int(input())
	p = input()
	q = input()
	s = []
	for i in range(n):
		if p[i] == '0' and q[i] == '0':
			s.append(1)
		elif p[i] == '0' and q[i] == '1':
			s.append(2)
		elif p[i] == '1' and q[i] == '0':
			s.append(2)
		else:
			s.append(0)
	ans1 = 0
	ans2 = 0
	ans = 0
	flag0 = False
	flag1 = False
	for i in range(n):
		if s[i] == 2:
			ans += 2
			if flag1:
				ans += 1
			flag0 = False
			flag1 = False
		elif s[i] == 1:
			if flag0:
				ans += 2
				flag0 = False
				flag1 = False
			elif flag1:
				ans += 1
			else:
				flag1 = True
		elif flag1:
			ans += 2
			flag0 = False
			flag1 = False
		else:
			flag0 = True
	if flag1:
		ans += 1
	return ans
for _ in range(int(input())):
	print(main())


for _ in range(int(input())):
	n = int(input())
	s1 = str(input())
	s2 = str(input())
	meow = sign = 0
	for i in range(n):
		if s1[i] != s2[i]:
			meow += 2
			sign = 0
		elif s1[i] == s2[i] == '1':
			if sign != 2:
				sign = 1
			else:
				meow += 1
				sign = 0
		elif sign != 1:
			meow += 1
			sign = 2
		else:
			meow += 2
			sign = 0
	print(meow)


from collections import defaultdict
import math
NO = 'NO'
YES = 'YES'
MOD = 1000000007
ALPH = 'abcdefghijklmnopqrstuvwxyz'

def input_int():
	return int(input())

def input_list():
	return input().split(' ')

def input_list_int():
	return list(map(int, input_list()))

def list_int_to_str(a, sep=' '):
	return sep.join((str(x) for x in a))
global_ans = []

def pr(a):
	global_ans.append(a)

def z_func(s):
	n = len(s)
	z = [0] * n
	l = r = 0
	for i in range(1, n):
		if r >= i:
			z[i] = min(z[i - l], r - i + 1)
		while z[i] + i < n and s[z[i]] == s[z[i] + i]:
			z[i] += 1
		if i + z[i] - 1 > r:
			l = i
			r = i + z[i] - 1
	return z

def is_prime(n):
	d = 2
	while n % d != 0:
		d += 1
	return d == n

def solve():
	n = input_int()
	a = [input(), input()]
	ans = 0
	cnt = {}
	for i in range(n - 1):
		if i not in cnt and a[0][i] == a[1][i] and (a[0][i + 1] == a[1][i + 1]) and (a[0][i] != a[0][i + 1]):
			ans += 2
			cnt[i] = 1
			cnt[i + 1] = 1
	tmp = defaultdict(int)
	for i in range(n):
		if i in cnt:
			tmp = defaultdict(int)
			continue
		tmp[a[0][i]] += 1
		tmp[a[1][i]] += 1
		if tmp['0'] > 0 and tmp['1'] > 0:
			ans += 2
			tmp = defaultdict(int)
		elif tmp['0'] > 0:
			ans += 1
			tmp = defaultdict(int)
	pr(ans)
query_count = 1
query_count = input_int()
while query_count:
	query_count -= 1
	solve()
for global_ans_line in global_ans:
	print(global_ans_line)


import bisect
import copy
import decimal
import fractions
import functools
import heapq
import itertools
import math
import random
import sys
from collections import Counter, deque, defaultdict
from functools import lru_cache, reduce
from heapq import heappush, heappop, heapify, heappushpop, _heappop_max, _heapify_max

def _heappush_max(heap, item):
	heap.append(item)
	heapq._siftdown_max(heap, 0, len(heap) - 1)

def _heappushpop_max(heap, item):
	if heap and item < heap[0]:
		(item, heap[0]) = (heap[0], item)
		heapq._siftup_max(heap, 0)
	return item
from math import degrees, gcd as GCD
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
T = int(readline())
for t in range(T):
	N = int(readline())
	S1 = readline().rstrip()
	S2 = readline().rstrip()
	ans = 0
	lst = []
	for (s1, s2) in zip(S1, S2):
		if s1 == s2:
			lst.append(int(s1))
		else:
			ans += 2
			while len(lst) >= 2:
				if lst[-1] != lst[-2]:
					ans += 2
					lst.pop()
					lst.pop()
				else:
					ans += 1 - lst.pop()
			if lst:
				ans += 1 - lst.pop()
	while len(lst) >= 2:
		if lst[-1] != lst[-2]:
			ans += 2
			lst.pop()
			lst.pop()
		else:
			ans += 1 - lst.pop()
	if lst:
		ans += 1 - lst.pop()
	print(ans)


for _ in range(int(input())):
	n = int(input())
	(s1, s2) = (input(), input())
	ans = 0
	skip = False
	for i in range(n):
		if skip:
			skip = False
			continue
		if s1[i] != s2[i]:
			ans += 2
		elif s1[i] == s2[i] == '1':
			if i + 1 <= n - 1:
				if s1[i + 1] == s2[i + 1] == '0':
					ans += 2
					skip = True
		elif s1[i] == s2[i] == '0':
			if i + 1 <= n - 1:
				if s1[i + 1] == s2[i + 1] == '1':
					ans += 2
					skip = True
				else:
					ans += 1
			else:
				ans += 1
	print(ans)


import sys
input = sys.stdin.readline
(T,) = map(int, input().split())
for _ in range(T):
	(N,) = map(int, input().split())
	s = input().strip()
	t = input().strip()
	R = 0
	for i in range(N):
		if s[i] == '1' and t[i] == '0':
			R += 2
		if s[i] == '0' and t[i] == '1':
			R += 2
		if s[i] == '0' and t[i] == '0':
			R += 1
	vs = set()
	us = set()
	for i in range(N):
		if s[i] == '0' and t[i] == '0' and (i != 0) and (s[i - 1] == '1') and (t[i - 1] == '1') and (i - 1 not in vs):
			R += 1
			vs.add(i - 1)
		elif s[i] == '0' and t[i] == '0' and (i != N - 1) and (s[i + 1] == '1') and (t[i + 1] == '1') and (i + 1 not in vs):
			R += 1
			vs.add(i + 1)
	print(R)


for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	c = 0
	flag0 = False
	flag1 = False
	for i in range(n):
		if a[i] == '0' or b[i] == '0':
			if flag0:
				if flag1:
					c += 2
				else:
					c += 1
				flag0 = False
				flag1 = False
				if a[i] == '0' or b[i] == '0':
					flag0 = True
				if a[i] == '1' or b[i] == '1':
					flag1 = True
			else:
				flag0 = True
				if a[i] == '0' or b[i] == '0':
					flag0 = True
				if a[i] == '1' or b[i] == '1':
					flag1 = True
		else:
			flag1 = True
		if flag0 and flag1:
			c += 2
			flag0 = False
			flag1 = False
	if flag0:
		if flag1:
			c += 2
		else:
			c += 1
	print(c)


import os
import sys
from io import BytesIO, IOBase
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))

def main():
	for _ in range(nmbr()):
		n = nmbr()
		s1 = input()
		s2 = input()
		p = ans = 0
		while p < n:
			this = s1[p] + s2[p]
			if p < n - 1 and (this == '00' and s1[p + 1] + s2[p + 1] == '11' or (this == '11' and s1[p + 1] + s2[p + 1] == '00')):
				ans += 2
				p += 2
			elif s1[p] + s2[p] in ['01', '10']:
				ans += 2
				p += 1
			elif s1[p] + s2[p] == '00':
				ans += 1
				p += 1
			else:
				p += 1
		sys.stdout.write(str(ans) + '\n')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for t in range(1):
	main()


t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	b = False
	ans = 0
	i = 0
	while i < n:
		if s1[i] == s2[i] == '1':
			b = True
		elif s1[i] != s2[i]:
			ans += 2
			b = False
		elif b == True:
			ans += 2
			b = False
		elif i < n - 1 and (s1[i + 1] == '1' and s2[i + 1] == '1'):
			ans += 2
			i += 1
		else:
			ans += 1
		i += 1
	print(ans)


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


def solve(a, b, n):
	ans = 0
	flag1 = False
	flag2 = False
	for i in range(n):
		if a[i] == '1' and b[i] == '1':
			if flag2:
				flag2 = False
				ans += 2
			else:
				flag1 = True
		elif a[i] == '0' and b[i] == '0':
			if flag1:
				flag1 = False
				ans += 2
			else:
				if flag2:
					ans += 1
				flag2 = True
		else:
			if flag2:
				ans += 1
			flag2 = False
			flag1 = False
			ans += 2
	if flag2:
		ans += 1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	print(solve(a, b, n))


for _ in range(int(input())):
	n = int(input())
	l = input()
	s = input()
	f = False
	fu = False
	ans = 0
	for i in range(n):
		if s[i] != l[i]:
			ans += 2
			f = False
			fu = False
		elif s[i] == '0' and f:
			ans += 2
			fu = False
			f = False
		elif s[i] == '0' and (not f):
			fu = True
			ans += 1
		elif s[i] == '1' and fu:
			ans += 1
			fu = False
			f = False
		else:
			f = True
	print(ans)


def solution(n):
	ans = 0
	ok = 0
	for x in range(n - 1):
		if ok:
			ok = 0
			continue
		if int(s[x]) + int(s1[x]) == 1:
			ans += 2
		elif s1[x] == s[x] == '0' and s1[x + 1] == s[x + 1] == '1' or (s1[x] == s[x] == '1' and (s1[x + 1] == '0' or s[x + 1] == '0')):
			ans += 2
			ok = 1
		elif s[x] == s1[x] == '0':
			ans += 1
	if not ok:
		if int(s1[-1]) + int(s[-1]) == 1:
			ans += 2
		elif s1[-1] == s[-1] == '0':
			ans += 1
	print(ans)
t = int(input())
for loop in range(t):
	n = int(input())
	s = input()
	s1 = input()
	solution(n)


t = int(input())
for _ in reversed(range(t)):
	tem = [0] * 2
	pre = -1
	f = int(input())
	a = input()
	b = input()
	ans = 0
	for i in range(f):
		x = int(a[i]) + int(b[i])
		if x == 1:
			if pre == 0:
				ans += 3
				pre = -1
			else:
				ans += 2
				pre = -1
		elif x == 2:
			if pre == 0:
				ans += 2
				pre = -1
			else:
				pre = 2
		elif pre == 2:
			ans += 2
			pre = -1
		elif pre == 0:
			ans += 1
		else:
			pre = 0
	if pre == 0:
		ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	arr = []
	for i in range(n):
		arr.append(int(s1[i]) + int(s2[i]))
	ans = 0
	i = 0
	while i < n:
		if arr[i] == 1:
			ans += 2
			i += 1
		elif arr[i] == 2:
			if i + 1 < n:
				if arr[i + 1] == 0 or arr[i + 1] == 1:
					ans += 2
					i += 2
				else:
					i += 1
			else:
				i += 1
		elif i + 1 < n:
			if arr[i + 1] == 2:
				ans += 2
				i += 2
			else:
				ans += 1
				i += 1
		else:
			ans += 1
			i += 1
	print(ans)


t = int(input())
for r in range(t):
	n = int(input())
	s_1 = input()
	s_2 = input()
	sum = 0
	i = 0
	prev = '-1'
	for i in range(n):
		if prev != '-1':
			if prev != s_1[i] and s_1[i] == s_2[i]:
				sum += 2
				prev = '-1'
				continue
			elif prev == '0':
				sum += 1
		if s_1[i] != s_2[i]:
			sum += 2
			prev = '-1'
		else:
			prev = s_1[i]
	if prev == '0':
		sum += 1
	print(sum)


import sys
input = sys.stdin.readline

def s1(k):
	if not k:
		return 0
	ans = 0
	taken = set()
	for i in range(len(k)):
		if k[i] == '0':
			if i - 1 >= 0 and k[i - 1] == '1' and (i - 1 not in taken):
				taken.add(i - 1)
				ans += 2
			elif i + 1 < len(k) and k[i + 1] == '1' and (i + 1 not in taken):
				taken.add(i + 1)
				ans += 2
			else:
				ans += 1
	return max(ans, k.count('0'))

def solve(a, b, n):
	ans = 0
	t = ''
	for i in range(n):
		if a[i] != b[i]:
			ans += 2 + s1(t)
			t = ''
		else:
			t += a[i]
	ans += s1(t)
	return ans
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	print(solve(a, b, n))


import sys
strings = iter(sys.stdin.read().split())
ints = (int(x) for x in strings)
sys.setrecursionlimit(3000)

def main():
	ntc = next(ints)
	for tc in range(1, ntc + 1):
		n = next(ints)
		a = [2 if x != y else 0 if x == '1' else 1 for (x, y) in zip(next(strings), next(strings))]
		ans = 0
		one_before = False
		zero_before = False
		for i in range(n):
			if a[i] == 2:
				ans += 2
				one_before = zero_before = False
			elif a[i] == 1:
				if zero_before:
					ans += 2
					one_before = zero_before = False
				else:
					ans += 1
					one_before = True
			elif one_before:
				ans += 1
				one_before = zero_before = False
			else:
				zero_before = True
		print(ans)
	return
main()


from collections import *
import math
from sys import *
import bisect
input = stdin.readline

def inp():
	return map(int, input().split())

def print_l(a):
	return stdout.write(' '.join(map(str, a)) + '\n')

def print_s(a):
	return stdout.write(str(a) + '\n')
for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	l = []
	for i in range(n):
		if int(s1[i]) + int(s2[i]) == 0:
			l.append(1)
		elif int(s1[i]) + int(s2[i]) == 1:
			l.append(2)
		else:
			l.append(0)
	k = len(l)
	for i in range(1, k):
		if l[i] + l[i - 1] == 1:
			l[i] = -1
			l[i - 1] = 2
	ans = 0
	for i in l:
		if i > 0:
			ans += i
	print(ans)


from collections import defaultdict

def calc_max_mex(s1, s2):
	n = len(s1)
	result = 0
	prev_state = None
	for i in range(n):
		if s1[i] != s2[i]:
			if prev_state == 0:
				result += 1
			result += 2
			prev_state = None
		elif s1[i] == '0' and s2[i] == '0':
			if prev_state == 0:
				result += 1
				prev_state = 0
			elif prev_state == 1:
				result += 2
				prev_state = None
			else:
				prev_state = 0
		elif prev_state == 0:
			result += 2
			prev_state = None
		elif prev_state == 1:
			prev_state = 1
		else:
			prev_state = 1
	if prev_state == 0:
		result += 1
	return result
n_samples = int(input())
for t in range(n_samples):
	n = int(input())
	s1 = input()
	s2 = input()
	assert len(s1) == n and len(s2) == n
	print(calc_max_mex(s1, s2))


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = input()
		b = input()
		i = 0
		answer = 0
		a += a[-1]
		b += b[-1]
		while i < n:
			if a[i] == '0' and b[i] == '0':
				if a[i + 1] == '1' and b[i + 1] == '1':
					answer += 2
					i += 2
				else:
					answer += 1
					i += 1
			elif a[i] == '1' and b[i] == '1':
				if a[i + 1] == '0' and b[i + 1] == '0':
					answer += 2
					i += 2
				else:
					i += 1
			else:
				answer += 2
				i += 1
		print(answer)
main()


for t in range(int(input())):
	n = int(input())
	one = [False] * n
	zero = [False] * n
	for _ in range(2):
		for (i, c) in enumerate(input()):
			if c == '1':
				one[i] = True
			else:
				zero[i] = True
	total = 0
	last = -1
	for i in range(n):
		if zero[i] and one[i]:
			total += 2
			last = -1
		elif zero[i]:
			total += 1
			if last == 1:
				total += 1
				last = -1
			else:
				last = 0
		elif last == 0:
			total += 1
			last = -1
		else:
			last = 1
	print(total)


import sys
import string
from decimal import Decimal
from math import log

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

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

def inpstrlist():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
t = int(input())
for _ in range(t):
	n = inp()
	A = input()
	B = input()
	c = 0
	i = 0
	while i < n:
		if A[i] != B[i]:
			c += 2
			i += 1
		else:
			if i != n - 1:
				if A[i] == A[i + 1] and B[i] == B[i + 1]:
					if A[i] == '0':
						c += 1
				else:
					if A[i] == '0' and int(A[i + 1]) + int(B[i + 1]) == 1:
						c += 1
					c += 2
					i += 1
			elif A[i] == '0':
				c += 1
			i += 1
	print(c)


def result(data1, data2):
	j = len(data1)
	score = 0
	compteur = 0
	while compteur < j:
		if data1[compteur] != data2[compteur]:
			score += 2
			compteur += 1
		elif compteur == j - 1:
			if data1[-1] == 0:
				score += 1
				compteur += 1
			else:
				compteur += 1
		elif data1[compteur] == 1:
			if data1[compteur + 1] == 0 or data2[compteur + 1] == 0:
				score += 2
				compteur += 2
			else:
				compteur += 1
		elif data1[compteur + 1] == 1 and data2[compteur + 1] == 1:
			score += 2
			compteur += 2
		elif data1[compteur + 1] != data2[compteur + 1]:
			score += 3
			compteur += 2
		else:
			score += 1
			compteur += 1
	return score
T = int(input())
for test_case in range(1, T + 1):
	trash = input()
	data1 = [int(i) for i in list(input())]
	data2 = [int(i) for i in list(input())]
	print(result(data1, data2))


T = int(input())
for t in range(T):
	n = int(input())
	s1 = input()
	s2 = input()
	arr = [int(s1[i] + s2[i], 2) for i in range(n)]
	ans = ind = 0
	for ind in range(n):
		if not arr[ind]:
			if ind > 0 and arr[ind - 1] == 3:
				ans += 2
			elif ind < n - 1 and arr[ind + 1] == 3:
				arr[ind + 1] = 4
				ans += 2
			else:
				ans += 1
		elif 1 <= arr[ind] <= 2:
			ans += 2
	print(ans)


def solve(s1, s2, n):
	res = 0
	i = 0
	while i < n:
		if s1[i] != s2[i]:
			res += 2
			i += 1
		elif s1[i] == '0':
			if i < len(s1) - 1:
				if s1[i + 1] == s2[i + 1] == '1':
					i += 2
					res += 2
				else:
					i += 1
					res += 1
			else:
				i += 1
				res += 1
		elif i < len(s1) - 1 and (s1[i + 1] == '0' or s2[i + 1] == '0'):
			i += 2
			res += 2
		else:
			i += 1
	print(res)

def parse_n_solve():
	t = int(input())
	for i in range(t):
		n = int(input())
		s1 = input()
		s2 = input()
		solve(s1, s2, n)
parse_n_solve()


import math
from collections import Counter, deque
from math import *
mod = 998244353

def solve():
	n = int(input())
	s1 = input()
	s2 = input()
	i = 0
	count1 = 0
	prev = -1
	while i < n:
		cur = s1[i] + s2[i]
		if '0' in cur and '1' in cur:
			count1 += 2
			if prev == 0:
				count1 += 1
			prev = -1
		elif '0' in cur:
			if prev == 1:
				count1 += 2
				prev = -1
			elif prev == 0:
				count1 += 1
				prev = 0
			else:
				prev = 0
		elif prev == -1 or prev == 1:
			prev = 1
		else:
			count1 += 2
			prev = -1
		i += 1
	if prev == 0:
		count1 += 1
	print(count1)
t = int(input())
for _ in range(t):
	solve()


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	for _ in range(1, ii() + 1):
		n = ii()
		s1 = si()
		s2 = si()
		(tot, one, zero) = (0, 0, 0)
		for i in range(n):
			if '0' in [s1[i], s2[i]] and '1' in [s1[i], s2[i]]:
				if zero:
					tot += 1
					zero = 0
				tot += 2
				one = 0
			elif '0' in [s1[i], s2[i]]:
				if one:
					tot += 2
					one = 0
				elif zero:
					tot += 1
					zero = 1
				else:
					zero = 1
			elif '1' in [s1[i], s2[i]]:
				if zero:
					tot += 2
					zero = 0
				else:
					one = 1
		if zero:
			tot += 1
		print(tot)
if file:
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


TESTS = int(input())
for t in range(TESTS):
	size = int(input())
	A = [int(x) for x in input()]
	B = [int(x) for x in input()]
	mex = 0
	previous = -1
	for i in range(size):
		(a, b) = (A[i], B[i])
		if a != b:
			mex += 2
			previous = -1
			continue
		if a + b == 0:
			mex += 1
			if previous == 1:
				mex += 1
				previous = -1
			else:
				previous = 0
		if a + b == 2:
			if previous == 0:
				mex += 1
				previous = -1
			else:
				previous = 1
	print(mex)


n = int(input())
for i in range(n):
	m = int(input())
	t = input()
	v = input()
	lastZeroUn = False
	lastOneUn = False
	ans = 0
	for j in range(m):
		if t[j] == '0' and v[j] == '0':
			if lastOneUn == True:
				ans += 2
				lastOneUn = False
			else:
				lastZeroUn = True
				ans += 1
		elif t[j] != '0' and v[j] != '0':
			if lastZeroUn == True:
				ans += 1
				lastZeroUn = False
			else:
				lastOneUn = True
		else:
			ans += 2
			lastZeroUn = False
			lastOneUn = False
	print(ans)


from collections import deque, Counter
from collections import defaultdict as dfd
from bisect import bisect, bisect_left
from math import sqrt, gcd, ceil, factorial, log2
from heapq import heapify, heappush, heappop
MOD = 10 ** 9 + 7
inf = float('inf')
ans_ = []

def nin():
	return int(input())

def ninf():
	return int(file.readline())

def st():
	return input().strip()

def stf():
	return file.readline().strip()

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

def readf():
	return list(map(int, file.readline().strip().split()))

def readfl():
	return list(map(float, input().strip().split()))

def readffl():
	return list(map(float, file.readline().strip().split()))

def solve():
	for _ in range(nin()):
		n = nin()
		s = st()
		t = st()
		ans = 0
		fl = 0
		ft = 0
		for i in range(n):
			if s[i] == t[i]:
				if s[i] == '0':
					ans += 1 + ft
					fl = 1 ^ ft
					ft = 0
				elif s[i] == '1':
					ans += fl
					ft = 1 ^ fl
					fl = 0
			else:
				ans += 2
				fl = 0
				ft = 0
		ans_.append(ans)
solve()
for i in ans_:
	print(i)


for i in range(int(input())):
	c = int(input())
	r1 = input()
	r2 = input()
	s = 0
	c0 = False
	c1 = False
	for i in range(c):
		if r1[i] == '0' and r2[i] == '1' or (r1[i] == '1' and r2[i] == '0'):
			s += 2
			c1 = False
			c0 = False
		elif r1[i] == '0' and r2[i] == '0':
			s += 1
			if c1:
				s += 1
				c1 = False
			else:
				c0 = True
		elif c0:
			s += 1
			c0 = False
		else:
			c1 = True
	print(s)


from sys import stdin, stdout
(input, print) = (stdin.readline, stdout.write)
from math import *

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(input())
		b = list(input())
		ans = 0
		k = 0
		f = 0
		for i in range(n):
			if int(a[i]) + int(b[i]) == 1:
				ans += 2
				f = 0
				k = 0
			elif int(a[i]) + int(b[i]) == 2 and k == 0:
				f = 1
			elif int(a[i]) + int(b[i]) == 2:
				ans += 1
				k = 0
				f = 0
			elif int(a[i]) + int(b[i]) == 0 and f == 1:
				ans += 2
				k = 0
				f = 0
			elif int(a[i]) + int(b[i]) == 0:
				k = 1
				ans += 1
		print(str(ans) + '\n')
main()


t = int(input())
inf = float('-inf')
for _ in range(t):
	n = input()
	s = list(map(lambda x: x == '1', input()))
	a = list(map(lambda x: x == '1', input()))
	sm = 0
	dp = [[[inf, inf] for j in range(2)] for _ in range(len(s))]
	dp[0][1 - (s[0] & a[0])][s[0] | a[0]] = (1 - (s[0] & a[0])) * (1 + (s[0] | a[0]))
	for i in range(1, len(s)):
		v = s[i] + a[i]
		if v == 2:
			dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][0][0], max((max(v) for v in dp[i - 1])))
			dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][1][0] + 1)
		elif v == 0:
			dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][0][0] + 1, max((max(v) for v in dp[i - 1])) + 1)
			dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][1] + 2)
		else:
			dp[i][1][1] = max(dp[i - 1][0][1] + 2, dp[i - 1][1][0] + 1, dp[i - 1][1][1], max((max(v) for v in dp[i - 1])) + 2)
	print(max((max(v) for v in dp[-1])))


for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	j = ans = 0
	for i in range(n):
		if j == 1 and (a[i] == '0' or b[i] == '0'):
			ans += 2
			j = 0
		elif j == 2 and (a[i] == '1' or b[i] == '1'):
			if a[i] == '1' and b[i] == '1':
				ans += 1
			else:
				ans += 2
			j = 0
		elif a[i] == '1' and b[i] == '1':
			j = 1
		elif a[i] == '0' and b[i] == '0':
			ans += 1
			j = 2
		elif a[i] == '0' and b[i] == '1' or (a[i] == '1' and b[i] == '0'):
			ans += 2
			j = 0
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	c = 0
	(p, q) = (0, 0)
	for i in range(n):
		if a[i] != b[i]:
			if p == 2:
				c += 1
			c += 2
			(p, q) = (0, 0)
		elif a[i] == '1':
			if p == 2:
				c += 2
				p = 0
			else:
				q = 2
		elif p == 2:
			c += 1
		elif q == 2:
			c += 2
			(p, q) = (0, 0)
		else:
			p = 2
	if p == 2:
		c += 1
	print(c)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections, string, bisect, re, random, queue, itertools, statistics, math
from collections import *
from bisect import *
from string import *
from itertools import *
from statistics import *
from math import *
from re import *
from queue import *

class Stack:

	def __init__(self):
		self.items = []

	def push(self, item):
		self.items.append(item)

	def pop(self):
		return self.items.pop()

	def empty(self):
		return self.items == []

	def size(self):
		return len(self.items)

	def at(self, idx):
		try:
			return self.items[idx]
		except:
			return -1

class priority_queue(object):

	def __init__(self):
		self.queue = []

	def __str__(self):
		return ' '.join([str(i) for i in self.queue])

	def empty(self):
		return len(self.queue) == 0

	def push(self, data):
		self.queue.append(data)

	def pop(self):
		try:
			max = 0
			for i in range(len(self.queue)):
				if self.queue[i] > self.queue[max]:
					max = i
			item = self.queue[max]
			del self.queue[max]
			return item
		except IndexError:
			print()
			exit()
mod = int(1000000000.0 + 7)
imax = float('inf')
imin = float('-inf')
true = True
false = False
N = int(100000.0 + 10)
none = None
inp = lambda : input()
I = lambda : int(inp())
M = lambda : map(int, inp().split())
MS = lambda : map(str, inp().split())
S = lambda : list(MS())
L = lambda : list(M())

def IO():
	try:
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('uttar.txt', 'w')
	except:
		pass
IO()

def kabraji_ka_totka():
	n = I()
	res = 0
	found = '2'
	for (i, j) in zip(inp(), inp()):
		if i != j:
			res += 2
			found = '2'
		else:
			res += i == '0'
			if i != found and found != '2':
				res += 1
				found = '2'
			else:
				found = i
	print(res)
for i in range(I()):
	kabraji_ka_totka()


t = int(input())
for i in range(t):
	k = int(input())
	a = input()
	b = input()
	ans = 0
	h = 3
	v = 0
	for j in range(k):
		if a[j] == '0':
			if b[j] == '0':
				if h == 1:
					h = 3
					v = 0
					ans += 2
				else:
					h = 0
					v += 1
			elif h != 0:
				ans += 2
				h = 3
				v = 0
			else:
				ans += 2 + v
				h = 3
				v = 0
		elif b[j] == '0':
			if h != 0:
				ans += 2
				h = 3
				v = 0
			else:
				ans += 2 + v
				h = 3
				v = 0
		elif h == 0:
			ans += 1 + v
			h = 3
			v = 0
		else:
			h = 1
	if h != 3:
		print(ans + (h + 1) % 2 * v)
	else:
		print(ans)


from collections import defaultdict
import math

def solve(seq1, seq2):
	last = -1
	total_mex = 0
	for i in range(len(seq1)):
		if seq1[i] != seq2[i]:
			total_mex += 2
			if last == 0:
				total_mex += 1
			last = -1
		elif last == -1:
			last = int(seq1[i])
		elif int(seq1[i]) != last:
			total_mex += 2
			last = -1
		elif last == 0:
			total_mex += 1
	if last == 0:
		total_mex += 1
	return total_mex
t = int(input())
for _ in range(t):
	_ = input()
	seq1 = input()
	seq2 = input()
	print(solve(seq1, seq2))


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp_vars_int = lambda : map(int, input().split())
inp_list_int = lambda : list(map(int, input().split()))
t = int(input())
for i in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	res = 0
	(found_0, found_1) = (False, False)
	for (c1, c2) in zip(s1, s2):
		c_sum = int(c1) + int(c2)
		if c_sum == 0:
			if found_1:
				res += 2
				(found_0, found_1) = (False, False)
			else:
				found_0 += 1
		elif c_sum == 1:
			res += 2 + found_0
			(found_0, found_1) = (False, False)
		elif c_sum == 2:
			if found_0:
				res += 1 + found_0
				(found_0, found_1) = (False, False)
			else:
				found_1 = True
	print(res + found_0)


def main():
	for _ in range(int(input())):
		n = int(input())
		a = input()
		b = input()
		ans = 0
		br = True
		curr = ''
		for i in range(n):
			if br:
				if a[i] != b[i]:
					ans += 2
				elif a[i] == '0':
					ans += 1
					br = False
					curr = '1'
				else:
					br = False
					curr = '0'
			elif a[i] != b[i]:
				ans += 2
				br = True
			elif curr in [a[i], b[i]]:
				if curr == '1':
					ans += 1
				else:
					ans += 2
				br = True
			elif curr == '1':
				ans += 1
				br = False
			elif curr == '0':
				br = False
		print(ans)
main()


import sys
input = sys.stdin.readline
import re
for _ in range(int(input())):
	n = int(input())
	w = ''.join(map(str, [i + j for (i, j) in zip(map(int, list(input()[:-1])), map(int, list(input()[:-1])))]))
	w = re.sub('20|02', '1', w)
	c = 0
	for i in w:
		if i == '1':
			c += 2
		elif i == '0':
			c += 1
	print(c)


import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
	n = int(input())
	st = list(input())
	rt = list(input())
	for i in range(n):
		st[i] = chr(st[i])
		rt[i] = chr(rt[i])
	ttt = [0 for i in range(n)]
	for i in range(n):
		ttt[i] = str(int(st[i]) + int(rt[i]))
	i = 0
	count = 0
	ttt.append('1')
	while i < n:
		if ttt[i] == '1':
			count += 2
			i += 1
		elif ttt[i] == '0' and ttt[i + 1] == '2':
			count += 2
			i += 2
		elif ttt[i] == '2' and ttt[i + 1] == '0':
			count += 2
			i += 2
		elif ttt[i] == '0':
			count += 1
			i += 1
		elif ttt[i] == '2':
			i += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	s = input().rstrip()
	t = input().rstrip()
	c = i = 0
	while i < n:
		if s[i] != t[i]:
			c += 2
			i += 1
		elif s[i] == '1':
			if i <= n - 2:
				if s[i + 1] == '0' and t[i + 1] == '0':
					c += 2
					i += 2
				else:
					c += 0
					i += 1
			else:
				c += 0
				i += 1
		elif i <= n - 2:
			if s[i + 1] == '1' and t[i + 1] == '1':
				c += 2
				i += 2
			else:
				c += 1
				i += 1
		else:
			c += 1
			i += 1
	print(c)


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input().rstrip()
	s2 = input().rstrip()
	ans = 0
	x = [False] * n
	y = [False] * n
	for i in range(n):
		if s1[i] != s2[i]:
			ans += 2
		elif s1[i] == s2[i] == '0':
			if i > 0 and y[i - 1]:
				ans += 2
				y[i - 1] = False
			else:
				ans += 1
				x[i] = True
		elif i > 0 and x[i - 1]:
			ans += 1
			x[i - 1] = False
		else:
			y[i] = True
	print(ans)


import time
import os, sys
from datetime import datetime
from math import floor, sqrt, gcd, factorial, ceil, log2
from collections import Counter, defaultdict
import bisect
from itertools import chain
from collections import deque
from sys import maxsize as INT_MAX
from itertools import permutations
from collections import deque
(ONLINE_JUDGE, INF, mod) = (False, float('inf'), int(1000000000.0) + 7)
if os.path.exists('D:\\vimstuff'):
	ONLINE_JUDGE = True
	sys.stdin = open('inp.txt', 'r')
	sys.stdout = open('out.txt', 'w')

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

def readstr():
	return sys.stdin.readline()

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

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

def mulfloat():
	return map(float, sys.stdin.readline().strip().split())

def flush():
	return sys.stdout.flush()

def power_two(x):
	return 1 << x

def lcm(a, b):
	return a * b // gcd(a, b)

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
			return n - leftGreater

def lower_bound(arr, n, val):
	(l, r) = (-1, n)
	while r > l + 1:
		m = int(l + r >> 1)
		if arr[m] < val:
			l = m
		else:
			r = m
	return r

def upper_bound(arr, n, val):
	(l, r) = (-1, n)
	while r > l + 1:
		m = int(l + r >> 1)
		if arr[m] <= val:
			l = m
		else:
			r = m
	return l

def binpow(a, n, mod):
	res = 1
	while n:
		if n & 1:
			res = res * a % mod
			n -= 1
		a = a * a % mod
		n = n >> 1
	return res

def printmat(l, seperate=True):
	for i in range(0, len(l)):
		if seperate:
			print(*l[i], sep=' ')
		else:
			print(*l[i], sep='')

def is_perfect_square(num):
	temp = num ** 0.5
	return temp // 1 == temp

def find(res):
	n1 = res
	while par[n1] != n1:
		par[n1] = par[par[n1]]
		n1 = par[n1]
	return n1

def union(u, v):
	(p1, p2) = (find(u), find(v))
	if p1 == p2:
		return 0
	if rank[p1] > rank[p2]:
		(p1, p2) = (p2, p1)
	par[p1] = p2
	rank[p2] += rank[p1]
	return 1

def john_3_16():
	n = readint()
	a = input()
	b = input()
	(cnt, i) = (0, 0)
	while i < n:
		if int(a[i]) == 1 - int(b[i]):
			cnt += 2
			i += 1
		elif i + 1 < n and a[i] == b[i] and (int(a[i + 1]) != 1 - int(b[i + 1])) and (a[i + 1] != a[i] or a[i + 1] != b[i] or b[i + 1] != a[i] or (b[i + 1] != b[i])):
			cnt += 2
			i += 2
		elif a[i] == b[i]:
			cnt += 1 - int(a[i])
			i += 1
	print(cnt)
	return

def main():
	tc = readint()
	start = time.time()
	while tc:
		john_3_16()
		tc -= 1
	if ONLINE_JUDGE:
		print(f'{(time.time() - start) * 1000}ms')
		pass
main()


from sys import stdin, stdout, setrecursionlimit
from io import BytesIO, IOBase
import math
setrecursionlimit(10000)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			a = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not a:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(a), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			a = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = a.count(b'\n') + (not a)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(a), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
input = lambda : stdin.readline().rstrip('\r\n')
inp = lambda : int(input())
st = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
int_arr = lambda : list(map(int, input().strip().split()))
str_arr = lambda : list(map(str, input().split()))
get_str = lambda : map(str, input().strip().split())
get_int = lambda : map(int, input().strip().split())
get_float = lambda : map(float, input().strip().split())
mod = 1000000007
for _ in range(inp()):
	n = inp()
	s1 = st()
	s2 = st()
	c = 0
	i = 0
	while i < n:
		if s1[i] != s2[i]:
			c += 2
			i += 1
		elif s1[i] == '0':
			j = i + 1
			if j == n:
				c += 1
				break
			if s1[j] == s2[j] == '1':
				c += 2
				i = j + 1
			else:
				c += 1
				i = j
		else:
			j = i + 1
			if j == n:
				break
			if s1[j] == s2[j] == '0':
				c += 2
				i = j + 1
			else:
				i = j
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = input()
	ans = 2 if s[0] != l[0] else 1 if s[0] == '0' else 0
	x = ans
	for i in range(1, n):
		if s[i] != l[i]:
			ans += 2
			x = 2
		elif x < 2 and (s[i] != s[i - 1] or s[i] != l[i - 1]):
			ans += 2 - x
			x = 2
		else:
			x = 1 if s[i] == '0' else 0
			ans += x
	print(ans)


from sys import stdin
input = stdin.readline

def answer():
	took = [False] * n
	(ans, i) = (0, 0)
	for i in range(n):
		if s[0][i] == '0' and s[1][i] == '0':
			ans += 1
			if i > 0 and (s[0][i - 1] == '1' and s[1][i - 1] == '1'):
				if not took[i - 1]:
					took[i] = True
					ans += 1
		elif s[0][i] == '0' and s[1][i] == '1':
			ans += 2
		elif s[0][i] == '1' and s[1][i] == '0':
			ans += 2
		elif i > 0 and (s[0][i - 1] == '0' and s[1][i - 1] == '0'):
			if not took[i - 1]:
				took[i] = True
				ans += 1
	return ans
for T in range(int(input())):
	n = int(input())
	s = [input().strip() for i in range(2)]
	print(answer())


def low(arr, key):
	(low, high) = (0,)
T = int(input())
for t in range(T):
	n = int(input())
	s = list(map(int, list(input())))
	t = list(map(int, list(input())))
	score = 0
	i = 0
	while i < n:
		if s[i] == t[i]:
			v = s[i]
			u = t[i]
			i += 1
			if i == n:
				score += 1 - v
				continue
			while i < n:
				if s[i] == 1 - t[i]:
					i -= 1
					score += 1 - v
					break
				else:
					if s[i] == v == t[i] == u:
						score += 1 - v
						i -= 1
						break
					if s[i] == 1 - v or t[i] == 1 - u:
						score += 2
						break
				i += 1
			else:
				score += 1 - v
		else:
			score += 2
		i += 1
	print(score)


t = int(input())
while t:
	t = t - 1
	n = int(input())
	string1 = input()
	string2 = input()
	count = 0
	i = 0
	while i < n:
		if i == n - 1:
			if string1[i] != string2[i]:
				count = count + 2
			elif string1[i] == '0' and string2[i] == '0':
				count = count + 1
			break
		if string1[i] != string2[i] and i < n - 1:
			count = count + 2
		elif string1[i] == '1':
			if string1[i + 1] == '0' or string2[i + 1] == '0':
				count = count + 2
				i = i + 1
		elif string1[i + 1] != string2[i + 1]:
			count = count + 3
			i = i + 1
		elif string1[i + 1] == '0' and string2[i + 1] == '0':
			count = count + 1
		else:
			count = count + 2
			i = i + 1
		i = i + 1
	print(count)