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.io.*;
import java.util.*;

public class Practice
{
//	static final long mod=7420738134811L;
	static int mod=1000000007;
	static final int size=1001;
	static FastReader sc=new FastReader(System.in);
//	static Reader sc=new Reader();
	static  PrintWriter out=new PrintWriter(System.out);
	static long[] factorialNumInverse;
	static long[] naturalNumInverse;	
	static long[] fact;
	public static void main(String[] args) throws IOException
	{
//		System.setIn(new FileInputStream("input.txt"));
//		System.setOut(new PrintStream("output.txt"));
//		naturalNumInverse=new long[size];
//		factorialNumInverse=new long[size];
//		fact=new long[size];
//		factorial(mod);
//		InverseofNumber(mod);
//		InverseofFactorial(mod);
		int t=1;
		t=sc.nextInt();
		while(t-->0)
		{
			solve();
//			sb.append("\n");
		}
//		out.print(sb);
		out.close();
		out.flush();
	}
	static void solve() throws IOException
	{
		int ans=0,n=sc.nextInt();
		String a=sc.next();
		String b=sc.next();
		for(int i=0;i<n;i++)
		{
			if(a.charAt(i)!=b.charAt(i))
				ans+=2;
			else
			{
				if(a.charAt(i)=='1')
				{
					if(i+1<n && a.charAt(i+1)==b.charAt(i+1) && a.charAt(i+1)=='0')
					{
						ans+=2;
						i++;
					}
				}
				else
				{
					if(i+1<n && a.charAt(i+1)==b.charAt(i+1) && a.charAt(i+1)=='1')
					{
						ans+=2;
						i++;
					}
					else
						ans++;
				}
			}
		}
		out.println(ans);
	}
	static class Pair implements Cloneable
	{
		int x,y;
		Pair(int a,int b)
		{
			this.x=a;
			this.y=b;
		}
		@Override
		public String toString() 
		{
			return "("+x+" at "+(y)+")";
		}
		@Override
		protected Pair clone() throws CloneNotSupportedException {
			return new Pair(this.x,this.y);
		}
	}
	static class Tuple implements Cloneable
	{
		int x,y,z;
		Tuple(int a,int b,int c)
		{
			this.x=a;
			this.y=b;
			this.z=c;
		}
		@Override
		public String toString() 
		{
			return "("+x+","+y+","+z+")";
		}
		@Override
		protected Tuple clone() throws CloneNotSupportedException {
			return new Tuple(this.x,this.y,this.z);
		}
	}
	static void arraySort(int arr[])
	{
		ArrayList<Integer> a=new ArrayList<Integer>();
		for (int i = 0; i < arr.length; i++) {
			a.add(arr[i]);
		}
		Collections.sort(a);
		for (int i = 0; i < arr.length; i++) {
			arr[i]=a.get(i);
		}
	}
	static void arraySort(long arr[])
	{
		ArrayList<Long> a=new ArrayList<Long>();
		for (int i = 0; i < arr.length; i++) {
			a.add(arr[i]);
		}
		Collections.sort(a);
		for (int i = 0; i < arr.length; i++) {
			arr[i]=a.get(i);
		}
	}
	public static void InverseofNumber(int p)
	{
	    naturalNumInverse[0] = naturalNumInverse[1] = 1;
	    for(int i = 2; i < size; i++)
	        naturalNumInverse[i] = naturalNumInverse[p % i] * (long)(p - p / i) % p;
	}
	// Function to precompute inverse of factorials
	public static void InverseofFactorial(int p)
	{
	    factorialNumInverse[0] = factorialNumInverse[1] = 1;
	    // pre-compute inverse of natural numbers
	    for(int i = 2; i < size; i++)
	        factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
	}
	// Function to calculate factorial of 1 to 200001
	public static void factorial(int p)
	{
	    fact[0] = 1;
	    for(int i = 1; i < size; i++)
	        fact[i] = (fact[i - 1] * (long)i) % p;
	}
	 
	// Function to return nCr % p in O(1) time
	public static long Binomial(int N, int R, int p)
	{
	     
	    // n C r = n!*inverse(r!)*inverse((n-r)!)
	    long ans = ((fact[N] * factorialNumInverse[R]) % p * factorialNumInverse[N - R]) % p;
	     
	    return ans;
	}
	static int findXOR(int x)	//from 0 to x
	{
		if(x<0)
			return 0;
		if(x%4==0)
			return x;
		if(x%4==1)
			return 1;
		if(x%4==2)
			return x+1;
		return 0;
	}
	static boolean isPrime(long x)
	{
		if(x==1)
			return false;
		if(x<=3)
			return true;
		if(x%2==0 || x%3==0)
			return false;
		for(int i=5;i<=Math.sqrt(x);i+=2)
			if(x%i==0)
				return false;
		return true;
	}
	static long gcd(long a,long b)
	{
		return (b==0)?a:gcd(b,a%b);
	}
	static int gcd(int a,int b)
	{
		return (b==0)?a:gcd(b,a%b);
	}
	static class UnionFind
	{
		  private int size;
		  private int[] sz;
		  private int[] parent;
		  private int numComponents;
		  public UnionFind(int size) 
		  {
		    if (size <= 0) throw new IllegalArgumentException("Size <= 0 is not allowed");
		    this.size = numComponents = size;
		    sz = new int[size];
		    parent = new int[size];
		    for (int i = 0; i < size; i++) 
		    {
		      parent[i] = i; 									// Link to itself (self root)
		      sz[i] = 1;								// Each component is originally of size one
		    }
		  }
		  public int find(int p) 
		  {
		    int root = p;
		    while (root != parent[root])
		    	root = parent[root];
		    while (p != root)
		    {
		      int next = parent[p];
		      parent[p] = root;
		      p = next;
		    }
		    return root;
		  }
		  public void makeParent(int p,int u)
		  {
			  parent[p]=u;
		  }
		  public boolean isConnected(int p, int q) 
		  {
		    return find(p) == find(q);
		  }
		  public int componentSize(int x) 
		  {
		    return sz[find(x)];
		  }
		  public int size() 
		  {
		    return size;
		  }
		  public int components() 
		  {
		    return numComponents;
		  }
		  public void unify(int p, int q) 
		  {
		    int root1 = find(p);
		    int root2 = find(q);
		    if(root1==root2)
		    {
		    	return;
		    }
		    else if (sz[root1] < sz[root2]) 
		    {
		    	parent[root1] = root2;
		    	sz[root2] += sz[root1];
		    	sz[root1] = 0;
		  } 
		    else 
		    {
		    	parent[root2] = root1;
		    	sz[root1] += sz[root2];
		    	sz[root2] = 0;
		    }
		    numComponents--;
		  }
		  void calc()
		  {
			  for(int i=0;i<size;i++)
				  find(i);
			  
		  }
	}
	static class Node
	{
		int vertex,dp;
		ArrayList<Edge> adj;
		ArrayList<Node> parent;
		Node(int v)
		{
			vertex=v;
			adj=new ArrayList<Edge>();
			parent=new ArrayList<Node>();
			dp=0;
		}
		@Override
		public String toString() 
		{
			return vertex+" ";
		}
	}
	static class Edge
	{
		Node to;
		int cost;
		Edge(Node t,int c)
		{
			this.to=t;
			this.cost=c;
		}
		@Override
		public String toString() {
			return "("+to.vertex+","+cost+") ";
		}
	}
	static long power(long x, long y)
	  {
	    long res = 1; 
	    x = x % mod; 
	    if (x == 0)
	      return 0; 
	    while (y > 0)
	    {
	    	if ((y & 1) != 0)
	    		res = (res * x) % mod;
	    	
	    	y = y >> 1; // y = y/2
	    	x = (x * x) % mod;
	    }
	    return res;
	  }
	static long binomialCoeff(long n, long k)
    {
        long res = 1;
//        if(k>n)
//        	return 0;
        // Since C(n, k) = C(n, n-k)
        if (k > n - k)
            k = n - k;
 
        // Calculate value of
        // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]
        for (long i = 0; i < k; ++i) {
            res *= (n - i);
            res /= (i + 1);
        }
 
        return res;
    }
	static class FastReader
	{
        byte[] buf = new byte[2048];
        int index, total;
        InputStream in;
 
        FastReader(InputStream is) 
        {
            in = is;
        }
 
        int scan() throws IOException 
        {
            if (index >= total) {
                index = 0;
                total = in.read(buf);
                if (total <= 0) {
                    return -1;
                }
            }
            return buf[index++];
        }
 
        String next() throws IOException 
        {
            int c;
            for (c = scan(); c <= 32; c = scan());
            StringBuilder sb = new StringBuilder();
            for (; c > 32; c = scan()) {
                sb.append((char) c);
            }
            return sb.toString();
        }
 
        int nextInt() throws IOException 
        {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan());
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
 
        long nextLong() throws IOException 
        {
            int c;
            long val = 0;
            for (c = scan(); c <= 32; c = scan());
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
    }
	static class Reader 
	{
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                                 BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
        public void printarray(int arr[])
        {
        	for (int i = 0; i < arr.length; i++)
				System.out.print(arr[i]+" ");
        	System.out.println();
        }
    }
}








