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

public class Main
{
    //static Scanner input= new Scanner();
    static FastReader input=new FastReader();
    //static UltraFastReader input = new UltraFastReader();
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    // Output format => out.append("Your Data")+"\n");
    
    
    
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		// Output format => out.append("Your Data")+"\n");

		int t = input.nextInt();
		while(t-->0){
		   int n = input.nextInt();
		   int len = n;
		   char [] s1 = input.next().toCharArray();
		   char [] s2 = input.next().toCharArray();
		   long res = 0;
		   for(int i=0;i<len;){
		       if(i<n && s1[i]==s2[i] && s1[i]=='0'){
		           if(i<len-1){
		               if(s1[i+1]==s2[i+1] && s1[i+1]=='1'){
		                   res += 2;
		                   i += 2;
		               }
		               else{
		                   res += 1;
		                   i += 1;
		               }
		           }
		           else{
		               res += 1;
		               i += 1;
		           }
		       }
		       else if(i<n && s1[i]==s2[i] && s1[i]=='1'){
		           if(i<len-1){
		               if(s1[i+1]==s2[i+1] && s1[i+1]=='0'){
		                   res += 2;
		                   i += 2;
		               }
		               else{
		                  
		                   i += 1;
		               }
		           }
		           else{
		               
		               i += 1;
		           }
		       }
		       else if(i<n){
		           res += 2;
		           i += 1;
		       }
		   }
		   
		   out.append(res+"\n");
		    
		}
		
		out.flush();
		out.close();
	}
	
	public static ArrayList<LinkedList<Integer>> createUndirectedGraph(int n, int m) throws IOException{
        //This function will create graph with n nodes and m edges.
        // It can also create a undirected tree if you pass value m as n-1
        ArrayList<LinkedList<Integer>> graph = new ArrayList<>();
        for(int i=0;i<=n;i++){
            graph.add(new LinkedList<>());
        }
        
        for(int i=1;i<=m;i++){
            int u = input.nextInt();
            int v= input.nextInt();
                graph.get(u).add(v);
                graph.get(v).add(u);
        }
        
        return graph;
    }
	
	
	static void merge(int arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;
 
        /* Create temp arrays */
        int L[] = new int[n1];
        int R[] = new int[n2];
 
        /*Copy data to temp arrays*/
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
 
        /* Merge the temp arrays */
 
        // Initial indexes of first and second subarrays
        int i = 0, j = 0;
 
        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
 
        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
 
        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
 
    // Main function that sorts arr[l..r] using
    // merge()
    static void mergeSort(int arr[], int l, int r)
    {
        if (l < r) {
            // Find the middle point
            int m =l+ (r-l)/2;
 
            // Sort first and second halves
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);
 
            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }
	
	public static int modPower(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
 
    if (x == 0)
      return 0; // In case x is divisible by p;
 
    while (y > 0)
    {
 
      // If y is odd, multiply x with result
      if ((y & 1) != 0)
        res = (res * x) % p;
 
      // y must be even now
      y = y >> 1; // y = y/2
      x = (x * x) % p;
    }
    return res;
  }
	
	 public static LinkedList<Integer> getDivisors(int n){
        LinkedList <Integer> res = new LinkedList<>();
        for(int i=1;i*i<=n;i++){
            if(n%i==0){
                res.add(i);
                if(i*i!=n){
                    res.add(n/i);
                }
            }
        }
        return res;
    }
    
    
    public static void printLL(LinkedList<Integer> ll) throws IOException{
        out.append("{");
        for(int i:ll){
            out.append(i+" ");
        }
        out.append("}\n");
    }
    
    public static boolean isPrime(int n) throws IOException{
        for(int i=2;i*i<=n;i++){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }
	
	
	//// Fast Reader Start
	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();
        }
        
        public String [] nextStrings(int n) throws IOException{
            String [] res = new String[n];
            for(int i=0;i<n;i++){
                res[i] = next();
            }
            return res;
        }
        
        int nextInt()
        {
            return Integer.parseInt(next());
        }
        
        public int [] nextInts(int n) throws IOException{
            int [] res = new int[n];
            for(int i=0;i<n;i++){
                res[i] = input.nextInt();
            }
            return res;
        }
        
        long nextLong()
        {
            return Long.parseLong(next());
        }
        
        public long [] nextLongs(int n) throws IOException{
            long [] res = new long[n];
            for(int i=0;i<n;i++){
                res[i] = input.nextLong();
            }
            return res;
        }
        
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
        
        public double [] nextDoubles(int n) throws IOException{
            double [] res = new double[n];
            for(int i=0;i<n;i++){
                res[i] = input.nextDouble();
            }
            return res;
        }
        
        String nextLine()
        {
            String str="";
            try
            {
                str=br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
    
    //// Fast Reader End
    
    
    //// Ultra Fast Reader Start
    
    static class UltraFastReader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public UltraFastReader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public UltraFastReader(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 int [] nextInts(int n) throws IOException{
            int [] res = new int[n];
            for(int i=0;i<n;i++){
                res[i] = input.nextInt();
            }
            return res;
        }
 
        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 long [] nextLongs(int n) throws IOException{
            long [] res = new long[n];
            for(int i=0;i<n;i++){
                res[i] = input.nextLong();
            }
            return res;
        }
 
        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;
        }
        
         public double [] nextDoubles(int n) throws IOException{
            double [] res = new double[n];
            for(int i=0;i<n;i++){
                res[i] = input.nextDouble();
            }
            return res;
        }
 
        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();
        }
    }
    //// Ultra Fast Reader End
    
}