There is a chessboard of size n by n. The square in the i-th row from top and j-th column from the left is labelled (i,j).

Currently, Gregor has some pawns in the n-th row. There are also enemy pawns in the 1-st row. On one turn, Gregor moves one of his pawns. A pawn can move one square up (from (i,j) to (i-1,j)) if there is no pawn in the destination square. Additionally, a pawn can move one square diagonally up (from (i,j) to either (i-1,j-1) or (i-1,j+1)) if and only if there is an enemy pawn in that square. The enemy pawn is also removed.

Gregor wants to know what is the maximum number of his pawns that can reach row 1?

Note that only Gregor takes turns in this game, and the enemy pawns never move. Also, when Gregor's pawn reaches row 1, it is stuck and cannot make any further moves.

Input

The first line of the input contains one integer t (1≤ t≤ 2⋅ 10^4) — the number of test cases. Then t test cases follow.

Each test case consists of three lines. The first line contains a single integer n (2≤ n≤ 2⋅{10}^{5}) — the size of the chessboard.

The second line consists of a string of binary digits of length n, where a 1 in the i-th position corresponds to an enemy pawn in the i-th cell from the left, and 0 corresponds to an empty cell.

The third line consists of a string of binary digits of length n, where a 1 in the i-th position corresponds to a Gregor's pawn in the i-th cell from the left, and 0 corresponds to an empty cell.

It is guaranteed that the sum of n across all test cases is less than 2⋅{10}^{5}.

Output

For each test case, print one integer: the maximum number of Gregor's pawns which can reach the 1-st row.

Example

Input


4
3
000
111
4
1111
1111
3
010
010
5
11001
00000


Output


3
4
0
0

Note

In the first example, Gregor can simply advance all 3 of his pawns forward. Thus, the answer is 3.

In the second example, Gregor can guarantee that all 4 of his pawns reach the enemy row, by following the colored paths as demonstrated in the diagram below. Remember, only Gregor takes turns in this "game"!

<image>

In the third example, Gregor's only pawn is stuck behind the enemy pawn, and cannot reach the end.

In the fourth example, Gregor has no pawns, so the answer is clearly 0.
1
20
01001100111111000100
00101100011010001110

8

# Author : devil9614 - Sujan Mukherjee

from __future__ import division, print_function

import os,sys
import math
import random
import collections
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
class my_dictionary(dict):
    def __init__(self):
        self = dict()
    def add(self,key,value):
        self[key] = value

def ii(): return int(input())
def si(): return input()
def mi(): return map(int,input().strip().split(" "))
def msi(): return map(str,input().strip().split(" "))
def li(): return list(mi())
def sli(): return list(msi())

def dmain():
    sys.setrecursionlimit(100000000)
    threading.stack_size(40960000)
    thread = threading.Thread(target=main)
    thread.start()
    
#from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
#from math import log,sqrt,factorial
#from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
#from decimal import *,threading
#from itertools import permutations
#Copy 2D list  m = [x[:] for x in mark] .. Avoid Using Deepcopy

abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]
def getKey(item): return item[1] 
def sort2(l):return sorted(l, key=getKey,reverse=True)
def d2(n,m,num):return [[num for x in range(m)] for y in range(n)]
def isPowerOfTwo (x): return (x and (not(x & (x - 1))) )
def decimalToBinary(n): return bin(n).replace("0b","")
def ntl(n):return [int(i) for i in str(n)]
def factorial(n): return 1 if (n==1 or n==0) else n * factorial(n - 1)
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(n-r))
def binary_search(arr, low, high, r,l,c): 
    if high >= low: 
  
        mid = (high + low) // 2
        if arr[mid] <= r or arr[mid] >= l: 
            c+=1
        elif arr[mid] > r: 
            return binary_search(arr, low, mid - 1, r,l,c) 
  
        else: 
            return binary_search(arr, mid + 1, high, r,l,c) 

  
    else: 
        return c
def ceil(x,y):
    if x%y==0:
        return x//y
    else:
        return x//y+1

def powerMod(x,y,p):
    res = 1
    x %= p
    while y > 0:
        if y&1:
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
    return res

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def nCr(n, r): 
  
    return (fact(n) / (fact(r)  
                * fact(n - r))) 
  
# Returns factorial of n 
def fact(n): 
  
    res = 1
      
    for i in range(2, n+1): 
        res = res * i 
          
    return res 

def printDivisors(n) :
     
    # Note that this loop runs till square root
    i = 1
    count = 0
    while i <= math.sqrt(n):
         
        if (n % i == 0) :
             
            # If divisors are equal, print only one
            if (n / i == i) :
                count+=1
            else :
                # Otherwise print both
                count+=1
        i = i + 1
    return count
def isPrime(n) : # Check Prime Number or not 
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True



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

def padded_bin_with_complement(x):
    if x < 0:
        return bin((2**16) - abs(x))[2:].zfill(16)
    else:
        return bin(x)[2:].zfill(16)
def binaryToDecimal(binary): 
      
    binary1 = binary 
    decimal, i, n = 0, 0, 0
    while(binary != 0): 
        dec = binary % 10
        decimal = decimal + dec * pow(2, i) 
        binary = binary//10
        i += 1
    return (decimal) 
def CountFrequency(my_list): 
    freq = {} 
    for item in my_list: 
        if (item in freq): 
            freq[item] += 1
        else: 
            freq[item] = 1
  
    return freq 
def pos(a):
    b = [0]*len(a)
    c = sorted(a)
    for i in range(len(a)):
        for j in range(len(a)):
            if c[j] == a[i]:
                b[i] = j
                break
    return b
def smallestDivisor(n): 
  
    # if divisible by 2 
    if (n % 2 == 0): 
        return 2
  
    # iterate from 3 to sqrt(n) 
    i = 3  
    while(i * i <= n): 
        if (n % i == 0): 
            return i 
        i += 2 
  
    return n
def commonn(a,b,n):
    c = []
    for i in range(n):
        if a[i] == b[i]:
            c.append("-1")
        else:
            c.append(b[i])
    return c


def find_lcm(num1, num2): 
    if(num1>num2): 
        num = num1 
        den = num2 
    else: 
        num = num2 
        den = num1 
    rem = num % den 
    while(rem != 0): 
        num = den 
        den = rem 
        rem = num % den 
    gcd = den 
    lcm = int(int(num1 * num2)/int(gcd)) 
    return lcm 

def sumdigit(n):
    n = str(n)
    k = 0
    for i in range(len(n)):
        k+=int(n[i])
    return k
def sort_list(list1, list2):
 
    zipped_pairs = zip(list2, list1)
 
    z = [x for _, x in sorted(zipped_pairs)]
     
    return z

from itertools import permutations
def isPerfectSquare(x):
 
    #if x >= 0,
    if(x >= 0):
        sr = math.sqrt(x)
         
        #return boolean T/F
        return ((sr*sr) == x)
    return False
def knapSack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]
 
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1]
                          + K[i-1][w-wt[i-1]], 
                              K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
 

    return K[n][W]
from collections import Counter
     
        
    
class Node:
    def __init__(self,val):
        self.next = None
        self.data = val
class linkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    def add(self,num):
        if self.head is None:
            self.head = Node(num)
            self.tail = self.head
        else:
            self.tail.next = Node(num)
            self.tail = self.tail.next
    def isLoop(self):
        if self.head is None:
            return False
        slow = self.head
        fast = self.head.next
 
        # Move slow and fast 1 and 2 steps respectively
        slow = slow.next
        fast = fast.next.next
 
        # Search for loop using slow and fast pointers
        while(slow != fast):
            if fast is None or fast.next == None:
                return False
            fast = fast.next.next
            slow = slow.next
        return True
    def loopHere(self,pos):
        if pos == 0:
            return 
        walk = self.head
        for _ in range(1,pos):
            walk = walk.next
        self.tail.next = walk
    def length(self):
        walk = self.head
        c = 0
        while(walk):
            c+=1
            walk = walk.next
        return c

from heapq import heappop, heappush, heapify
def sort_k(arr, n, k):
    heap = arr[:k + 1]
    heapify(heap)
    target_index = 0
    for rem_elmnts_index in range(k + 1, n):
        arr[target_index] = heappop(heap)
        heappush(heap, arr[rem_elmnts_index])
        target_index += 1
 
    while heap:
        arr[target_index] = heappop(heap)
        target_index += 1
import string
def main():
    # print(10)
    # for _ in range(10):
    #     h = random.randint(1,1000)
    #     print(h)

    for _ in range(int(input())):
        n = ii()
        b = si()
        a = si()
        visited = {}
        count = 0
        for i in range(n):
            if a[i] == "0":
                continue
            if i == 0:
                if b[i] == "0":
                    count+=1
                elif b[i+1] == "1":
                    count+=1
                    visited[i+1] = 1
            elif i == n-1:
                if b[i] == "0":
                    count+=1
                elif b[i-1] == "1" and ((i-1) not in visited):
                    count+=1
                    visited[i-1] = 1
            elif a[i] == "1" and b[i] == "0":
                count+=1
            elif (a[i] == "1") and (b[i-1] == "1" or b[i+1] == "1"):
                if b[i-1] == "1" and ((i-1) not in visited):
                    count+=1
                    visited[i-1] = 1
                elif b[i+1] == "1" and ((i+1) not in visited):
                    count+=1
                    visited[i+1] = 1
        print(count)
        


        




# def main():
    # print(100)
    # for i in range(100):
    #     print(50)
    #     print(*(sorted(random.sample(range(1000),50))))
    #     print(*(sorted(random.sample(range(1000),50))))
    #     print(*(sorted(random.sample(range(1000),50))))
    # for i in range(int(input())):
    #     n = int(input())
    #     arr1 = list(map(int, input().split()))
    #     arr2 = list(map(int, input().split()))
    #     arr3 = list(map(int, input().split()))
    #     print(*(Solution().smallestDifferenceTriplet(arr1,arr2,arr3,n)))
    

# region fastio
# template taken from https://github.com/cheran-senthil/PyRival/blob/master/templates/template.py

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):
    """Prints the values to a stream, or to sys.stdout by default."""
    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")

# endregion


if __name__ == "__main__":
    #read()
    main()