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

import java.io.*;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;










public class Codeforces2 {
    static String ab,b;
    static class Node
    {
        int val;
        Node left;
        Node right;
        public Node(int x) {
            // TODO Auto-generated constructor stub
            this.val=x;
            this.left=null;
            this.right=null;
        }
    }
    static class Pair<U, V> implements Comparable<Pair<U, V>> {
        public U x;
        public V y;

        public Pair(U x, V y) {
            this.x = x;
            this.y = y;
        }

        public int compareTo(Pair<U, V> o) {
            int value = ((Comparable<U>) x).compareTo(o.x);
            if (value != 0) return value;
            return ((Comparable<V>) y).compareTo(o.y);
        }

        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            return x.equals(pair.x) && y.equals(pair.y);
        }

        public int hashCode() {
            return Objects.hash(x, y);
        }

    }
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
        int[] nextArray(int n)
        {
            int arr[]=new int[n];
            for(int i=0;i<n;i++)
                arr[i]=nextInt();
            return arr;
        }
    }
    static String string;
    static int gcd(int a, int b)
    {
        // Everything divides 0 
        if (a == 0)
            return b;
        if (b == 0)
            return a;

        // base case
        if (a == b)
            return a;

        // a is greater
        if (a > b)
            return gcd(a%b, b);
        return gcd(a, b%a);
    }
    static int gcd(int a, int b,boolean[] prime)
    {
        // Everything divides 0 
        if (a == 0)
            return b;
        if (b == 0)
            return a;

        // base case
        if (a == b)
            return a;
        if(prime[a]&&prime[b])
            return 1;
        // a is greater
        if (a > b)
            return gcd(a%b, b);
        return gcd(a, b%a);
    }
    static long gcd(long a, long b)
    {
        // Everything divides 0 

        for(long i=2;i<=b;i++)
        {
            if(a%i==0&&b%i==0)
                return i;
        }
        return 1;
    }
    static int fac(int n)
    {
        int c=1;
        for(int i=2;i<n;i++)
            if(n%i==0)
                c=i;
        return c;
    }


    static int lcm(int a,int b)
    {
        for(int i=Math.min(a, b);i<=a*b;i++)
            if(i%a==0&&i%b==0)
                return i;
        return 0;
    }
    static int maxHeight(char[][] ch,int i,int j,String[] arr)
    {
        int h=1;
        if(i==ch.length-1||j==0||j==ch[0].length-1)
            return 1;
        while(i+h<ch.length&&j-h>=0&&j+h<ch[0].length&&ch[i+h][j-h]=='*'&&ch[i+h][j+h]=='*')
        {
            String whole=arr[i+h];
            //System.out.println(whole.substring(j-h,j+h+1));
            if(whole.substring(j-h,j+h+1).replace("*","").length()>0)
                return h;
            h++;
        }

        return h;
    }
    static boolean all(BigInteger n)
    {
        BigInteger c=n;
        HashSet<Character> hs=new HashSet<>();
        while((c+"").compareTo("0")>0)
        {
            String d=""+c;
            char ch=d.charAt(d.length()-1);
            if(d.length()==1)
            {
                c=new BigInteger("0");

            }
            else
                c=new BigInteger(d.substring(0,d.length()-1));
            if(hs.contains(ch))
                continue;
            if(d.charAt(d.length()-1)=='0')
                continue;
            if(!(n.mod(new BigInteger(""+ch)).equals(new BigInteger("0"))))
                return false;
            hs.add(ch);
        }
        return  true;
    }

    static int cal(long n,long k)
    {
        System.out.println(n+","+k);
        if(n==k)
            return 2;
        if(n<k)
            return 1;
        if(k==1)
            return 1+cal(n, k+1);
        if(k>=32)
            return 1+cal(n/k, k);
        return 1+Math.min(cal(n/k, k),cal(n, k+1));
    }
    static Node buildTree(int i,int j,int[] arr)
    {
        if(i==j)
        {

            //System.out.print(arr[i]);
            return new Node(arr[i]);
        }
        int max=i;
        for(int k=i+1;k<=j;k++)
        {
            if(arr[max]<arr[k])
                max=k;
        }
        Node root=new Node(arr[max]);
        //System.out.print(arr[max]);
        if(max>i)
            root.left=buildTree(i, max-1, arr);
        else {
            root.left=null;
        }
        if(max<j)
            root.right=buildTree(max+1, j, arr);
        else {
            root.right=null;
        }
        return root;
    }
    static int height(Node root,int val)
    {
        if(root==null)
            return Integer.MAX_VALUE-32;
        if(root.val==val)
            return 0;
        if((root.left==null&&root.right==null))
            return Integer.MAX_VALUE-32;
        return Math.min(height(root.left, val), height(root.right, val))+1;
    }
    static void shuffle(int a[], int n)
    {
        for (int i = 0; i < n; i++) {

            // getting the random index 
            int t = (int)Math.random() * a.length;

            // and swapping values a random index 
            // with the current index 
            int x = a[t];
            a[t] = a[i];
            a[i] = x;
        }
    }
    static void sort(int[] arr )
    {
        shuffle(arr, arr.length);
        Arrays.sort(arr);
    }
    static int helper(int i,boolean flag,int n,int c,int val,int[][][] dp)
    {
        if(i<=0||i>=n+1)
        {
            c++;
            return 1;
        }
        int last=flag?1:0;
        if(dp[i][val][last]!=0)
            return dp[i][val][last];
        int ans=0;
        if(flag)
        {
            ans=helper(i+1, flag, n, c, val,dp);
            if(val>1)
                ans+=helper(i-1, !flag, n, c, val-1,dp);
        }
        else {
            ans=helper(i-1, flag, n, c, val,dp);
            if(val>1)
                ans+=helper(i+1, !flag, n, c, val-1,dp);
        }
        return dp[i][val][last]=ans;
    }
    static boolean valid(char[] arr,int k)
    {
        int[] count=new int[26];
        for(int i=0;i<arr.length;i++)
            count[(int)arr[i]-'a']++;
        for(int i=0;i<26;i++)
            if(count[i]%k!=0)
                return false;
        return true;
    }

    static int compute(int c,int r)
    {
        if(r<c/2)
            r=c-r;
        int ans=1;
        for(int i=c;i>r;i--)
            ans*=i;
        int fac=fac(c-r);
        return ans/fac;
    }
    static boolean arraySortedInc(int arr[], int n)
    {

        // Array has one or no element
        if (n == 0 || n == 1)
            return true;

        for (int i = 1; i < n; i++)

            // Unsorted pair found
            if (arr[i - 1] > arr[i])
                return false;

        // No unsorted pair found
        return true;
    }
    static boolean arraySortedDec(int arr[], int n)
    {

        // Array has one or no element
        if (n == 0 || n == 1)
            return true;

        for (int i = 1; i < n; i++)

            // Unsorted pair found
            if (arr[i - 1] > arr[i])
                return false;

        // No unsorted pair found
        return true;
    }
    static int largestPower(int n, int p) {
        // Initialize result
        int x = 0;

        // Calculate x = n/p + n/(p^2) + n/(p^3) + ....
        while (n > 0) {
            n /= p;
            x += n;
        }
        return x;
    }

    // Utility function to do modular exponentiation.
// It returns (x^y) % p
    static int power(int x, int y, int p) {
        int res = 1; // Initialize result
        x = x % p; // Update x if it is more than or
        // equal to p
        while (y > 0) {
            // If y is odd, multiply x with result
            if (y % 2 == 1) {
                res = (res * x) % p;
            }

            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }
        return res;
    }

    // Returns n! % p
    static int modFact(int n, int p) {
        if (n >= p) {
            return 0;
        }

        int res = 1;

        // Use Sieve of Eratosthenes to find all primes
        // smaller than n
        boolean isPrime[] = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = 2 * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // Consider all primes found by Sieve
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                // Find the largest power of prime 'i' that divides n
                int k = largestPower(n, i);

                // Multiply result with (i^k) % p
                res = (res * power(i, k, p)) % p;
            }
        }
        return res;
    }
    static boolean helper(int[][] all,int row,int[] count)
    {
//		System.out.println(new String(arr)+","+i+","+a+","+b);
        if(row==all.length)
            return true;
//		System.out.println(all[row][row]);
//		for(int i=0;i<all.length;i++)
//			System.out.println(Arrays.toString(all[i]));
//		System.out.println();
//		System.out.println();
        if(count[all[row][row]]==all[row][row])
            return helper(all, row+1, count);
        else {
            for(int i=0;i<all.length;i++)
            {
                for(int j=0;j<=i;j++)
                {
                    if(all[i][j]==all[row][row])
                    {
//						System.out.println(row+","+i+","+j);
                        if(j>0&&all[i][j-1]==0)
                        {
                            all[i][j-1]=all[row][row];
                            count[all[row][row]]++;
                            if(helper(all, row, count))
                                return true;
                            else {
                                all[i][j-1]=0;
                                count[all[row][row]]--;
                            }
                        }
                        if(j<i&&all[i][j+1]==0)
                        {
                            all[i][j+1]=all[row][row];
                            count[all[row][row]]++;
                            if(helper(all, row, count))
                                return true;
                            else {
                                all[i][j+1]=0;
                                count[all[row][row]]--;
                            }
                        }
                        if(i<all.length-1&&all[i+1][j]==0)
                        {
                            all[i+1][j]=all[row][row];
                            count[all[row][row]]++;
                            if(helper(all, row, count))
                                return true;
                            else {
                                all[i+1][j]=0;
                                count[all[row][row]]--;
                            }
                        }
                        if(i>0&&j!=i&&all[i-1][j]==0)
                        {
                            all[i-1][j]=all[row][row];
                            count[all[row][row]]++;
                            if(helper(all, row, count))
                                return true;
                            else {
                                all[i-1][j]=0;
                                count[all[row][row]]--;
                            }
                        }

                    }
                }
            }
            return false;
        }
    }
    static List<Integer> helper(List<Integer> list)
    {
        int sum=0;
        for(int i:list)
            sum+=i;
        sum/=list.size();
        boolean in=false;
        List<Integer> temp=new ArrayList<>(list);
        for(Integer i:list)
        {
            if(i>sum)
            {
                in=true;
                temp.remove(i);
            }
        }
        if(temp.equals(list))
            return temp;
        return helper(temp);
    }
    static int helper(char[] arr,boolean reversed,int alice,int bob,int c)
    {
        int in=-1,count=0,st=-1;
        for(int i=0;i<=arr.length/2;i++)
        {
            if(arr[i]=='0'&&arr[arr.length-1-i]=='1')
            {
                in=i;
                break;
            }
            else if(arr[i]=='1'&&arr[arr.length-1-i]=='0')
            {
                in=arr.length-1-i;
                break;
            }
            if(arr[i]=='0')
            {
                if(st==-1)
                    st=i;
                count++;
            }
            if(arr[arr.length-i-1]=='0')
            {
                if(st==-1)
                    st=arr.length-1-i;
                count++;
            }
        }
        System.out.println(in);
        if(count==0)
        {
            return alice-bob;
        }
        else if(arr.length%2!=0&&arr[arr.length/2]=='0')
        {
            arr[arr.length/2]='1';
            return helper(arr, false, alice, bob, count);
        }
        if(in==-1||reversed)
        {
            arr[st]='1';
            if(c%2==0)
                return helper(arr, false, alice+1, bob, c+1);
            else {
                return helper(arr, false, alice, bob+1, c+1);
            }
        }
        else {
            arr[in]='1';
            return helper(arr, true, alice, bob, c+1);
        }
    }
    static boolean[] seiveOfErathnos(int n2)
    {
        boolean isPrime[] = new boolean[n2 + 1];
        Arrays.fill(isPrime, true);
        for (int i = 2; i * i <= n2; i++) {
            if (isPrime[i]) {
                for (int j = 2 * i; j <= n2; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        return isPrime;
    }
    static boolean[] seiveOfErathnos2(int n2,int[] ans)
    {
        boolean isPrime[] = new boolean[n2 + 1];
        Arrays.fill(isPrime, true);
        for (int i = 2; i * i <= n2; i++) {
            if (isPrime[i]) {
                for (int j = 2 * i; j <= n2; j += i) {
                    if(isPrime[j])
                        ans[i]++;
                    isPrime[j] = false;
                }
            }
        }
        return isPrime;
    }
    public static void main(String[] args)throws IOException
    {
        BufferedReader bReader=new BufferedReader(new InputStreamReader(System.in));
        FastReader fs=new FastReader();
//        int[] ans=new int[1000001];
        int T=fs.nextInt();
//        seiveOfErathnos2(1000000, ans);
        StringBuilder sb=new StringBuilder();
        while(T-->0)
        {
//            long n = fs.nextLong();
        	int n=fs.nextInt();
        	char[] enemy=fs.nextLine().toCharArray();
        	char[] greg=fs.nextLine().toCharArray();
        	int ans=0;
        	if(enemy[0]=='1'&&greg[1]=='1')
        	{
        		ans++;
        		enemy[0]='@';
        		greg[1]='0';
        	}
        	if(enemy[n-1]=='1'&&greg[n-2]=='1')
        	{
        		ans++;
        		enemy[n-1]='@';
        		greg[n-2]='0';
        	}
        	for(int i=0;i<n;i++)
        	{
        		if(enemy[i]=='0')
        		{
        			if(greg[i]=='1')
        			{
        				ans++;
        				greg[i]='0';
        			}
        		}
        		else if(enemy[i]=='1')
        		{
        			if(i>0&&greg[i-1]=='1')
        			{
        				ans++;
        				greg[i-1]='0';
        			}
        			else if(i<n-1&&greg[i+1]=='1')
        			{
        				ans++;
        				greg[i+1]='0';
        			}
        		}
        	}
        	sb.append(ans);
            sb.append("\n");
        }
        System.out.println(sb);
    }
}