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.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

public class Chess {
    static HashSet<String> memo = new HashSet<String>();
    
    public static void subsecuencias(String datos) {
        System.out.print("[");
        for(int i=0;i<datos.length();i++)
            System.out.print(datos.charAt(i)+", ");
        System.out.println("]");
        memo.add(datos);
        for (int i=0;i<datos.length();i++){
            String nuevoDatos = datos.substring(0,i)+datos.substring(i+1);
            
            if (!memo.contains(nuevoDatos))
                subsecuencias(nuevoDatos);
        }
    }
    
    public static void subsecuencias(ArrayList<Integer> datos, ArrayList<Integer> datosT) {
        
        
        for (int i=0;i<datos.size();i++){
            ArrayList<Integer> datosNuevo = new ArrayList<>();
            for (int h=0;h<datos.size();h++){
                if (h!=i){
                    //System.out.print(datos.get(h));
                    datosNuevo.add(datos.get(h));
                }
            }
            
            if(!datosNuevo.isEmpty())
                subsecuencias(datosNuevo, datosT);
            
        }
        for (int i=0;i<datos.size();i++){
            System.out.print(datos.get(i)+".");
        }
        System.out.println();
    }
    
    public static int solucion(int[] datos) {
        double sum1 = datos [0];
        double sum2 = 0.0;
               
        for (int i=1;i<datos.length;i++)
            sum2+=datos[i];
        double maximo = sum1 + sum2 / (datos.length-1);
        
        //System.out.println(sum1+" "+sum2+" "+maximo);
        
        
        for (int i=1;i<datos.length;i++){
            sum1 += datos[i];
            sum2 -= datos[i];
            System.out.println(sum1+" "+sum2+" "+maximo);
        }
        
        
        
        return 0;
    }
    public static void main22(String[] args) {
        //int[] datos = {3,1,2};
        //int ret = solucion(datos);
        //System.out.println(ret);
        ArrayList<Integer> datos = new ArrayList<>();
        for (int i = 0;i<6;i++)            
            datos.add(i);
        
        subsecuencias(datos,datos);
        //datos.add(1);
        //datos.add(2);
        //datos.add(3);
        //datos.add(40);
        //datos.add(5);
        
        
        
        //System.out.println((1 << 6));
        /*
        int n= 5;
        List<List<Boolean>> powerSet = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) {
            List<Boolean> subset = new ArrayList<>(n);
            for (int j = 0; j < n; j++)
                subset.add(((1 << j) & i) > 0);
            powerSet.add(subset);
        }
        
        for (int i=0;i<powerSet.size();i++){
            List<Boolean> subset = powerSet.get(i);
            System.out.print("[");
            for (int h=0;h<subset.size();h++){
                if(subset.get(h))
                    System.out.print("1 ");
                else
                    System.out.print("0 ");
            }
            System.out.println("]");
        }*/
    }
    
    
    public static int pawn(String scr, String dst) {
        int tot = 0;
        int acumdst = 0;
        int acumscr = 0;
        scr += "0";
        dst += "0";
        for (int i=0;i<dst.length();i++){
            if (dst.charAt(i)=='0'){
                if (acumscr<acumdst){
                    tot += acumscr;
                }
                else
                if (acumscr>0){
                    if (acumscr % 2==0)
                        tot += acumscr;
                    else    
                        tot += acumscr - 1;
                }
                if (scr.charAt(i)=='1'){
                    tot++;
                }
                //System.out.println(i+" " + acumdst + " " + acumscr + " " + tot);
                acumdst = 0;
                acumscr = 0;
                
            }
            else{
                acumdst++;
                if (scr.charAt(i)=='1'){
                    acumscr++;
                }
            }
        }
        
        return tot;
    }
    
    public static String reemplazar(String str, int pos, char car) {
        StringBuilder cad = new StringBuilder(str);
        cad.setCharAt(pos, car);
        return cad.toString();
    }
    
    public static int contar(String scr) {
        int ret = 0;
        for (int i=0;i<scr.length();i++)
            if (scr.charAt(i)=='X')
                ret++;
        return ret;
    }
    static int maximo = 0;
    static HashSet<String> memo2 = new HashSet<String>();
    public static void pawn2(String scr, String dst) {
        String x = scr+dst;
        if (memo2.contains(x))
            return;
        memo2.add(x);
        
        //System.out.println(scr+"\t"+dst);
        //System.out.println("==============");
        for (int i=0;i<scr.length();i++){
            for (int h=-1;h<=1;h++){
                int pos = h+i;
                if (pos>=0 && pos <scr.length()){
                    //System.out.println(pos+" ");
                    
                    if (i==pos){
                        if (scr.charAt(pos)=='1' && dst.charAt(pos)=='0'){
                            String dstNuevo = reemplazar(dst,pos,'X');
                            String scrNuevo = reemplazar(scr,pos,'0');
                            //System.out.println(scrNuevo+"\t"+dstNuevo);
                            pawn2(scrNuevo, dstNuevo);
                            int nuevo = contar(dstNuevo);
                            if (nuevo>maximo)
                                maximo = nuevo;
                        }
                    }
                    else{
                        if (scr.charAt(i)=='1' && dst.charAt(pos)=='1'){
                            String dstNuevo = reemplazar(dst,pos,'X');
                            String scrNuevo = reemplazar(scr,i,'0');
                            //System.out.println(scrNuevo+"\t"+dstNuevo);
                            pawn2(scrNuevo, dstNuevo);
                            int nuevo = contar(dstNuevo);
                            if (nuevo>maximo)
                                maximo = nuevo;
                        }
                    }
                }
            }
            //System.out.println("..............");
        }
    }
    
    public static int pawnAux(String scr, String dst) {
        int ret = 0;
        scr += "0";
        dst += "0";
        String scrNuevo = "" + scr.charAt(0);
        String dstNuevo = "" + dst.charAt(0);
        for (int i=1;i<dst.length();i++){
            if (dst.charAt(i)=='0'){
                System.out.println(scrNuevo + " \\ " + dstNuevo);
                maximo = 0;
                memo2.clear();
                pawn2(scrNuevo, dstNuevo);
                
                ret += maximo;
                if (scr.charAt(i)=='1')
                    ret++;
                
                scrNuevo = "";
                dstNuevo = "";
            }
            else{
                scrNuevo +=  scr.charAt(i);
                dstNuevo +=  dst.charAt(i);
            }
        }
        return ret;
    }
    
    /*
    public static int pawnLineal(String scr, String dst) {
        int ret = 0;
        scr = "0" + scr + "0";
        dst = "0" + dst + "0";
        for (int i=1;i<scr.length()-1;i++){
            //System.out.print(scr.charAt(i));
        
            if (scr.charAt(i)=='1'){
                if (dst.charAt(i-1)=='1'){
                    dst = reemplazar(dst,i-1,'X');
                    ret++;
                }
                else
                if (dst.charAt(i)=='0'){
                    dst = reemplazar(dst,i,'X');
                    ret++;
                }
                else
                if (dst.charAt(i+1)=='1'){
                    dst = reemplazar(dst,i+1,'X');
                    ret++;
                }
            }
        } 
        return ret;
    }    
   */
    public static int pawnLineal(String scr1, String dst1) {
        int ret = 0;
        scr1 = "0" + scr1 + "0";
        dst1 = "0" + dst1 + "0";
        
        StringBuilder scr = new StringBuilder(scr1);
        StringBuilder dst = new StringBuilder(dst1);
        
        for (int i=1;i<scr.length()-1;i++){
            //System.out.print(scr.charAt(i));
        
            if (scr.charAt(i)=='1'){
                if (dst.charAt(i-1)=='1'){
                    dst.setCharAt(i-1,'X');
                    ret++;
                }
                else
                if (dst.charAt(i)=='0'){
                    dst.setCharAt(i,'X');
                    ret++;
                }
                else
                if (dst.charAt(i+1)=='1'){
                    dst.setCharAt(i+1,'X');
                    ret++;
                }
            }
        } 
        return ret;
    }    
        
    public static void main(String[] args) {
        /*maximo = 0;
        String scr = "111011111100000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000011101011011100111010111001";//"101011";
        String dst = "101011011100101011111010001110011111111110000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000111110";//"111011";
        System.out.println("lineal "+pawnLineal(scr, dst));
        */
        /*scr = dst = "";
        for (int i=0;i<200000;i++){
            
        }*/
        //pawn2(scr, dst);
        //System.out.println("maximo "+maximo);
        
        //System.out.println("pawnAux " + pawnAux(scr, dst));
        /*
        maximo = 0;
        memo2.clear();
        String scr = "10101";
        String dst = "11111";
        pawn2(scr, dst);
        System.out.println("maximo "+maximo);
        
        int ret = pawnAux(scr, dst);
        System.out.println(ret);
        System.out.println("...............");
        System.out.println("lineal "+pawnLineal(scr, dst));
        */
        //System.out.println(ret);
        /*
        System.out.println("...............................");
        
        ret = pawn("111", "010");
        System.out.println(ret);
        */
        
        
        Scanner sc = new Scanner(System.in);
        String largo = sc.nextLine();
        int casos = Integer.parseInt(largo);
        for (int i=0;i<casos;i++){
            largo = sc.nextLine();
            //System.out.println(largo);
            String scr = sc.nextLine();
            //System.out.println(scr);
            String dst = sc.nextLine();
            //System.out.println(dst);
            //System.out.println((i+1)+"\t"+pawn(dst, scr));
            //maximo = 0;
            //memo2.clear();
            //pawn2(dst, scr);
            //System.out.println(pawnAux(dst, scr));
            System.out.println(pawnLineal(dst, scr));
        }
        
    }
}
