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 ≤ t ≤ 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 ≤ n ≤ 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.

Example

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.
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
#import threading
'''Dont use setrecursionlimit in pypy'''
#sys.setrecursionlimit(int(1e9)+500)
#threading.stack_size(0x2000000)
ONLINE_JUDGE,INF,mod=False,float('inf'),int(1e9)+7
if os.path.exists('D:\\vimstuff'):
	ONLINE_JUDGE=True
	sys.stdin=open('inp.txt','r')
	sys.stdout=open('out.txt','w')
'''def ceil(a,b):
	return(int((a+b-1)/b))'''

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):
	#print(num)
	temp = num**(0.5)
	#print(temp)
	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


'''
c-space = to copy
o-space= to open file
,-space=to run prog
:noh= to get rid of text highlight

1. Implement after understanding properly don't do in vain.
2. Check corner cases.
3. Use python if there is recursion,try-catch,dictionary.
4. Use pypy if heavy loop,list slice.
'''
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
		else:
			if(i+1<n and a[i]==b[i] 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()
	#tc=1
	#cnt=0
	start=time.time()
	#cnt=1
	while tc:
		john_3_16()
		tc-=1
		#cnt+=1
	if ONLINE_JUDGE:
		print(f'{(time.time()-start)*1000}ms')
		pass
main()