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 java.util.*;
import java.io.*;
public class Solution{ 


static int[] p,sz;
static int mod=1000000007,cc=0;	
static int find(int x) {
	   if(x==p[x])
		   return x;
	   return p[x]= find(p[x]);
}
static void union(int x,int y) {
	    int rx = find(x),ry=find(y);
	    if(rx==ry)
	    	return;
	    else {
	    	p[rx]=ry;
	    	sz[ry]=sz[ry]+sz[rx];
	    	cc--;
	    }
}
public static void main(String[] args)throws Exception
{  
	// System.out.println("enter a number:");


       
     int  t= ni();
     for(int u=1;u<=t;u++) {
          int n = ni();
          char s1[]= n().toCharArray();
          char s2[] = n().toCharArray();
          int s[] =new int[n];
          
          for(int i=0;i<n;i++) 
        	  s[i] = (s1[i]-'0') +(s2[i]-'0');
          int ans=0;
          
          for(int i=0;i<n;i++) {
        	  if(s[i]==1) ans=ans+2;
        	  else if(s[i]==0) {
        		  if((i+1)<n&&s[i+1]==2) {ans=ans+2; i++;}
        		  else ans++;
        	  }
        	  else {
        		  if((i+1)<n&&s[i+1]==0) {
        			  ans=ans+2;
        			  i++;
        		  }  
        	  }
          }
    out.println(ans);

     }
      out.flush();
}
static HashMap<Integer,Integer> gethm(int a[]){ // this function will give a hasmap of an array
	 HashMap<Integer,Integer> hm = new HashMap();
	 for(int i=0;i<a.length;i++)
		 if(hm.containsKey(a[i]))
			 hm.put(a[i], hm.get(a[i])+1);
		 else
			 hm.put(a[i], 1);
	 return hm;
}
static void tmap(HashMap<Integer,Integer> hm) {  // function to traverse a map.
	
	 for(Map.Entry<Integer,Integer> e: hm.entrySet()) {
		 int k = e.getKey();
		 int v = e.getValue();
		 System.out.println(" key:"+k+" val:"+v);
	 }
}
////////////////////////// solution ends ////////////////////////////////////////////////
static class pair
	{
		int l,k;
		pair(){}
		pair(int c,int d){l=c;k=d;}
		/*@Override
		public int hashCode(){return (a+" "+b).hashCode();}
		@Override public boolean equals(Object c){if(a==((pair)c).a&&b==((pair)c).b)return true;return false;} */
	}  
static void seive(boolean p[]){

                    p[0]=true; p[1]=true;
                for(int i=2;i*i<p.length;i++)
                   if(p[i]==false){
                    for(int j=i*i;j<p.length;j=j+i)
                         p[j]=true;
                  }
             }
static int get(int index)
        {
                return (index&(-index));
        }
static void add(int bit[],int index,int val)
        {
             while(index<bit.length)
               {
                    bit[index] = bit[index]+val;
                    index = index + get(index);
               }
        }
static int get(int bit[],int index)
         {
               int sum=0;
               while(index>0)
                {
                    sum = sum+bit[index];
                    index = index-get(index);
                }
              return sum;
         }
static void add(long bit[],int index,long val)
        {
             while(index<bit.length)
               {
                    bit[index] = bit[index]+val;
                    index = index + get(index);
               }
        }
static long get(long bit[],int index)
         {
               long sum=0;
               while(index>0)
                {
                    sum = sum+bit[index];
                    index = index-get(index);
                }
              return sum;
         } 
static void compress(int a[])
         {      
                int n = a.length;
                Integer ar[] = new Integer[n];
                for(int i=0;i<n;i++)
                     ar[i] = a[i];
                Arrays.sort(ar);
                HashMap<Integer,Integer> hm = new HashMap();
                int st=1;
                for(int i=0;i<n;i++)
                    if(!hm.containsKey(ar[i]))
                        hm.put(ar[i],st++);
                for(int i=0;i<n;i++)
                   a[i] = hm.get(a[i]);
         }
static int find(int x,int p[]){ if(x==p[x]) return x; return p[x]=find(p[x],p) ;}
static void union(int x,int y,int p[]){ int xr=find(x,p),yr=find(y,p); if(xr!=yr){ p[xr]=yr;} }
 
static int abs(int x){ return x>0 ? x : -x; }
static long abs(long x){ return x>0 ? x : -x; }
static long gcd(long a,long b){ if(a==0)return b; if(b==0) return a;if(b%a==0) return a;return gcd(b%a,a); }
static int gcd(int a,int b){ if(a==0)return b; if(b==0) return a; if(b%a==0) return a;return gcd(b%a,a); }
static long min(long a,long b){ return a<b ? a : b; }
static int min(int a,int b){ return a<b ? a : b; }
static long max(long a,long b){ return a>b ? a : b; }
static int max(int a,int b){ return a>b ? a : b; }
static long pow(long a,long b,long md){ long ans=1;  while(b>0){if(b%2==1) ans = (ans*a)%md; a = (a*a)%md; b = b/2;} return ans; }
static int log2n(long a){ int te=0; while(a>0) {a>>=1; ++te; } return te; }

static void reverse(int a[]){int i1=0,i2=a.length-1; while(i1<i2){int t = a[i1];a[i1]=a[i2];a[i2]=t;i1++;i2--;}  } 
static void reverse(long a[]){ int i1=0,i2=a.length-1; while(i1<i2){ long t = a[i1]; a[i1]=a[i2];a[i2]=t;i1++;i2--;}  } 

static void subtract_1(char s[]){if(s[0]=='0') return;int n = s.length,i=n-1;while(s[i]=='0')i--;s[i] =(char)((int)(s[i]-'0') + 47);for(int j=i+1;j<n;j++)s[j]='9';}
static void reverse(char s[]){int i1=0,i2=s.length-1; while(i1<i2){char t=s[i1];s[i1]=s[i2];s[i2]=t; i1++;i2--;} }
static String reverse(String r){String s = "";int i= r.length()-1; while(i>=0){ s=s+r.charAt(i);i--;}return s;}
static boolean pal(char s[]){ int i1=0,i2=s.length-1; while(i1<i2){ if(s[i1]!=s[i2]) return false; i1++;i2--;} return true;}
static boolean pal(String s){int n = s.length(),i1=0,i2=n-1;while(i1<i2){if(s.charAt(i1)!=s.charAt(i2))return false;i1++; i2--;}return true;}
 
// Input OutPut Functions
static PrintWriter out = new PrintWriter(System.out);
static FastReader sc=new FastReader();
static int ni(){ int x = sc.nextInt();return(x); }
static long nl(){ long x = sc.nextLong(); return(x); }

static String n(){ String str = sc.next(); return(str); }
static String ns(){ String str = sc.nextLine(); return(str);}
static double nd(){double d = sc.nextDouble(); return(d); }
static char nch() {char ch = sc.next().charAt(0); return ch; }
static int[] ai(int n){ int a[] = new int[n]; for(int i=0;i<n;i++) a[i] = ni(); return a; }
static long[] al(int n) {long a[] = new long[n]; for(int i=0;i<n;i++) a[i] = nl(); return a; }
static double[] ad(int n) { double a[]= new double[n]; for(int i=0;i<n;i++) a[i]=nd(); return a;} 
static String[] as(int n){ String a[] = new String[n]; for(int i=0;i<n;i++) a[i] = n(); return a; }
static void p(Object o){ out.print(o); }
static void pn(Object o){ out.println(o); } 
 
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;} 
  } 
}