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.
////solution at bottom 
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

     public class test
{
         
    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[][] tdiarr(int m , int n){
            int[][] a = new int[m][n];
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    a[i][j]=Integer.parseInt(next());
                }
            }
            return a;
        }
        long[][] tdlarr(int m , int n){
            long[][] a = new long[m][n];
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    a[i][j]=Long.parseLong(next());
                }
            }
            return a;
        }
 
        int[] niarr(int n)
        {
            int[] a = new int[n];
            for(int i=0;i<n;i++)a[i]=Integer.parseInt(next());
            return a;
        }
        long[] nlarr(int n)
        {
            long[] a = new long[n];
            for(int i=0;i<n;i++)a[i]=Long.parseLong(next());
            return a;
        }
        char[] ncarr(){
            return next().trim().toCharArray();
            
            
        }
        
  
        int ni() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nl() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nd() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nstr() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
     
    
     
    static FastReader br=new FastReader();
/*
 
*/
///////////////////////////////////////////////////////////
 
 
 
 
 
    public static void main (String[] args) throws java.lang.Exception
    {
         try{
             System.setIn(new FileInputStream("input.txt"));
             System.setOut(new PrintStream(new FileOutputStream("output.txt")));
        }
        catch(Exception e){
             }
 long start__time = System.currentTimeMillis();
 
         
        int t=1;
        br=new FastReader();
                       t=br.ni();
  
         
  
     in1 :   for(int TC = 1; TC <= t ; TC++)
        {
             
                solve();
               
 
 
     
        }
          
             
        System.out.println(sb);
       
long end__time = System.currentTimeMillis();
long elapsed__time = end__time - start__time;
System.err.println(elapsed__time);

    }
    ///end main
     static StringBuilder sb = new StringBuilder();
    
    static void solve() throws Exception{
                 
               int n = br.ni();
               char[][] a = new char[2][n];
               for(int i=0;i<2;i++)a[i] = br.ncarr();
                int ans = 0;
            for(int i=0;i<n;i++){
                 if(a[0][i] == '0' && a[1][i] == '0')ans++;
                 else if(a[0][i] == '1' && a[1][i] == '1')ans+=0;
                 else ans+=2;
            }
            boolean[] vis = new boolean[n];
            for(int i=0;i<n;i++){
                if(a[0][i] == '1' && a[1][i] == '1'){
                    if(i-1>=0 && !vis[i-1] && a[0][i-1]=='0' && a[1][i-1]=='0'){
                        ans++;
                        vis[i-1] = true;
                    }
                    else if(i+1<n && !vis[i+1] && a[0][i+1]=='0' && a[1][i+1]=='0'){
                        ans++;
                        vis[i+1] = true;
                    }
                }
            }
            sb.append(ans+"\n");


    }
                    
    //end solve
     
 

     
              
    }
    //end class  
 
    /* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
  
 TC:
   
 
 
      */   

          
