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.awt.Container;
import java.awt.image.SampleModel;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.concurrent.CountDownLatch;

import javax.naming.TimeLimitExceededException;

import java.io.PrintStream;


public class Solution {

	static class Pair<T,V>{
		T first;
		V second;
		public Pair(T first, V second) {
			super();
			this.first = first;
			this.second = second;
		}

	}

	// public static final boolean LOCAL = System.getProperty("ONLINE_JUDGE")==null;
	private static FastScanner fs=new FastScanner();
	private static Scanner sc=new Scanner(System.in);
	
	private static int uperBound(long[] arr, long val) {
		
		int start= 0; 
		int end=arr.length;
		while(start<end) {
			int mid=(start+end)/2;
			if( arr[mid]==val ) {
				return mid;
			}
			if( arr[mid]>val ) {
				end=mid-1;
			}else {
				start=mid+1;
			}
		}
		
		if( start >= arr.length || arr[start]>val) {
			return start;
		}else {
			return start+1;
		}
		
	}

	private static void solve(int TC) throws Exception{
		/*WRITE CODE HERE*/

		
		int len=fs.nextInt();
		String row1=fs.next();
		String row2=fs.next();
		
		int prev=-1;
		int count=0;
		
		for(int i=0;i<len; i++) {
			if( row1.charAt(i) != row2.charAt(i) ) {
				count+=2;
				prev=-1;
			}else if ( row1.charAt(i)=='1') {
				if(prev==0) {
					count++;
					prev=-1;
				}else {
					prev=1;
				}
			}else {
				if(prev==1) {
					count+=2;
					prev=-1;
				}else {
					count++;
					prev=0;
				}
			}
		}
		
		System.out.println(count);
		
		/*int a=fs.nextInt();
		int b=fs.nextInt();
		int c=fs.nextInt();
		int m=fs.nextInt();
		
		int max=a+b+c-3;
		
		int arr[]= {a,b,c};
		Arrays.parallelSort(arr);
		
		int min=arr[2]-arr[1]-arr[0]-1;
		if(m>=min && m<=max) {
			System.out.println("YES");
		}else {
			System.out.println("No");
		}
		*/
		/*
		int n=fs.nextInt();
		long hero[]=new long[n];
		long sum=0;
		for(int i=0;i<n;i++) {
			hero[i]=Long.parseLong(fs.next());
			sum+=hero[i];
		}
		//System.out.println(sum);
		Arrays.sort(hero);
		//for(long x: hero)
			//System.out.print(x+" ");
		//System.out.println();
		int m=fs.nextInt();
		while(m-->0) {
			
			long df=Long.parseLong(fs.next());
			long at=Long.parseLong(fs.next());
			
			
			
			long nextGrt=(long)Math.pow(10, 18);
			long nextSmall=-1;
			int index=uperBound(hero, df);
			//System.out.println(hero[index]);
			//System.out.println(index);
			if(index>=n) {
				nextSmall=hero[n-1];
			}else if(index<=0 ) {
				nextGrt=hero[0];
			}else {
				nextGrt=hero[index];
				nextSmall=hero[index-1];
			}
			
			/*for(int i=0;i<n;i++) {
				if(hero[i]>=df &&  hero[i]<nextGrt  ) {
					nextGrt=hero[i];
				}
				if(hero[i]<=df && hero[i]>nextSmall ) {
					nextSmall=hero[i];
				}
			}
			
			//System.out.println(nextGrt +" : "+nextSmall);
		
			if( nextGrt!= (long) Math.pow(10, 18) && sum-nextGrt >=at ) {
				System.out.println(0);
			}else {
				if(nextGrt==(long)Math.pow(10, 18)) {
					
					long ans= df- nextSmall;
					ans+= ( at<= ( sum-nextSmall ) ) ? 0 : (at- sum+nextSmall);
					System.out.println(ans);
				}
				else if(nextSmall==-1) {
					long ans= ( at <= sum- nextGrt ) ? 0 : ( at- sum+nextGrt);
					System.out.println(ans);
				}else {
					long ans1=df- nextSmall;
					ans1+= ( at<= ( sum-nextSmall ) ) ? 0 : (at- sum+nextSmall);
					
					long ans2= ( at <= sum- nextGrt ) ? 0 : ( at- sum+nextGrt);
					
					System.out.println(Math.min(ans1, ans2));
				}
			}
			
			
			
		}
		
		
		/*int n=fs.nextInt();
		
		for(int i=1;i<=n;i++) {
			String open="";
			String close="";
			for(int j=1;j<=i;j++) {
				open+="(";
				close+=")";
			}
			
			int j=0;
			while( j+2*i <= 2* n) {
				System.out.print(open);
				System.out.print(close);
				j=j+2*i;
			}
			//System.out.println(j);
			if(j<2*n) {
				while(j<2*n) {
					System.out.print("(");
					System.out.print(")");
					j+=2;
				}
			}
			System.out.println();
		}
		
*/

	}

	public static void main(String[] args) throws Exception {

		int tcr=1; 
		//tcr = sc.nextInt();
		tcr=fs.nextInt();

		while(tcr-->0) {
			solve(tcr);

		}

		System.gc();

	}

	
	static int computeXOR(int n)
	{
		// If n is a multiple of 4
		if (n % 4 == 0)
			return n;

		// If n%4 gives remainder 1
		if (n % 4 == 1)
			return 1;

		// If n%4 gives remainder 2
		if (n % 4 == 2)
			return n + 1;

		// If n%4 gives remainder 3
		return 0;
	}
	
	static boolean isSorted (int[] nums) {

		for (int i = 0; i < nums.length - 1; i++) {

			if (nums[i] > nums[i + 1]) {

				return false;

			}

		}

		return true;

	}

	static void firstOperation (int[] nums) {

		for (int i = 1; i < nums.length; i += 2) {

			int temp = nums[i];
			nums[i] = nums[i - 1];
			nums[i - 1] = temp;

		}

	}

	static void secondOperation (int[] nums) {

		int n = nums.length / 2;

		for (int i = 0; i < n; i++) {

			int temp = nums[i];
			nums[i] = nums[i + n];
			nums[i + n] = temp;

		}

	}


	private static long numOfDigits(long a) {
		long ans=0;
		while(a!=0) {
			ans++;
			a/=10;
		}
		return ans;
	}

	private static String reverse(String s) {
		String ans="";
		for(int i=s.length()-1;i>=0;i--) {
			ans+=s.charAt(i);
		}
		return ans;
	}

	private static boolean isPalindrome(String s) {
		int i=0;
		int j=s.length()-1;

		while(i<j) {
			if(s.charAt(i)!=s.charAt(j)) {
				return false;
			}
			i++;
			j--;
		}
		return true;
	}

	static class FastScanner {

		BufferedReader br;
		StringTokenizer st ;

		FastScanner(){
			br =  new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer("");
		}

		FastScanner(String file) {

			try {
				br =  new BufferedReader(new InputStreamReader(new FileInputStream(file)));
				st = new StringTokenizer("");
			} catch (FileNotFoundException e) {
				// TODO Auto-generated catch block
				System.out.println("file not found");
				e.printStackTrace();
			}

		}


		String next() {
			while (!st.hasMoreTokens())
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
				}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}
		String readLine() throws IOException{
			return br.readLine();
		}
	}

	public static long[] sort(long arr[]){
		List<Long> list = new ArrayList<>();
		for(long n : arr){list.add(n);}
		Collections.sort(list);
		for(int i=0;i<arr.length;i++){
			arr[i] = list.get(i);
		}
		return arr;
	}
	public static int[] sort(int arr[]){
		List<Integer> list = new ArrayList<>();
		for(int n : arr){list.add(n);}
		Collections.sort(list);
		for(int i=0;i<arr.length;i++){
			arr[i] = list.get(i);
		}
		return arr;
	}

	// return the (index + 1)
	// where index is the pos of just smaller element
	// i.e count of elemets strictly less than num
	public static int justSmaller(long arr[],long num){
		//  System.out.println(num+"@");
		int st = 0;
		int e = arr.length - 1;

		int ans = -1;

		while(st <= e){

			int mid = (st + e)/2;

			if(arr[mid] >= num){
				e = mid - 1;
			}else{
				ans = mid;
				st = mid + 1;
			}

		}


		return ans + 1;

	}

	//return (index of just greater element)
	//count of elements smaller than or equal to num

	public static int justGreater(long arr[],long num){
		int st = 0;
		int e = arr.length - 1;

		int ans = arr.length;

		while(st <= e){

			int mid = (st + e)/2;

			if(arr[mid] <= num){
				st = mid + 1;
			}else{
				ans = mid;
				e = mid - 1;
			}
		}

		return ans;

	}


	public static boolean isPrime(int n) {

		for(int i=2;i<n;i++) {
			if(n%i==0) {
				return false;
			}
		}
		return true;
	}

	public static void println(Object obj){
		System.out.println(obj.toString());
	}

	public static void print(Object obj){
		System.out.println(obj.toString());
	}

	public static long gcd(long a,long b){
		if(b == 0l){
			return a;
		}

		return gcd(b,a%b);
	}

	public static int find(int parent[],int v){
		if(parent[v] == v){
			return v;
		}

		return parent[v] = find(parent, parent[v]);
	}



	public static List<Integer> sieve(){

		List<Integer> prime = new ArrayList<>();

		int arr[] = new int[100001];

		Arrays.fill(arr,1);

		arr[1] = 0;
		arr[2] = 1;

		for(int i=2;i<=100000;i++){

			if(arr[i] == 1){

				prime.add(i);

				for(long j = (i*1l*i);j<100001;j+=i){
					arr[(int)j] = 0;
				}
			}
		}

		return prime;
	}

	static boolean isPower(long n,long a){

		long log = (long)(Math.log(n)/Math.log(a));

		long power = (long)Math.pow(a,log);

		if(power == n){return true;}

		return false;
	}


	private static int mergeAndCount(int[] arr, int l,int m, int r)
	{

		// Left subarray
		int[] left =  Arrays.copyOfRange(arr, l, m + 1);

		// Right subarray
		int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);

		int i = 0, j = 0, k = l, swaps = 0;

		while (i < left.length && j < right.length) {
			if (left[i] <= right[j])
				arr[k++] = left[i++];
			else {
				arr[k++] = right[j++];
				swaps += (m + 1) - (l + i);
			}
		}
		while (i < left.length)
			arr[k++] = left[i++];
		while (j < right.length)
			arr[k++] = right[j++];
		return swaps;
	}

	// Merge sort function
	private static int mergeSortAndCount(int[] arr, int l,int r)
	{

		// Keeps track of the inversion count at a
		// particular node of the recursion tree
		int count = 0;

		if (l < r) {
			int m = (l + r) / 2;

			// Total inversion count = left subarray count
			// + right subarray count + merge count

			// Left subarray count
			count += mergeSortAndCount(arr, l, m);

			// Right subarray count
			count += mergeSortAndCount(arr, m + 1, r);

			// Merge count
			count += mergeAndCount(arr, l, m, r);
		}

		return count;
	}

	static class Debug {
		//change to System.getProperty("ONLINE_JUDGE")==null; for CodeForces
		public static final boolean LOCAL = System.getProperty("ONLINE_JUDGE")==null;
		private static <T> String ts(T t) {
			if(t==null) {
				return "null";
			}
			try {
				return ts((Iterable) t);
			}catch(ClassCastException e) {
				if(t instanceof int[]) {
					String s = Arrays.toString((int[]) t);
					return "{"+s.substring(1, s.length()-1)+"}\n";
				}else if(t instanceof long[]) {
					String s = Arrays.toString((long[]) t);
					return "{"+s.substring(1, s.length()-1)+"}\n";
				}else if(t instanceof char[]) {
					String s = Arrays.toString((char[]) t);
					return "{"+s.substring(1, s.length()-1)+"}\n";
				}else if(t instanceof double[]) {
					String s = Arrays.toString((double[]) t);
					return "{"+s.substring(1, s.length()-1)+"}\n";
				}else if(t instanceof boolean[]) {
					String s = Arrays.toString((boolean[]) t);
					return "{"+s.substring(1, s.length()-1)+"}\n";
				}
				try {
					return ts((Object[]) t);
				}catch(ClassCastException e1) {
					return t.toString();
				}
			}
		}
		private static <T> String ts(T[] arr) {
			StringBuilder ret = new StringBuilder();
			ret.append("{");
			boolean first = true;
			for(T t: arr) {
				if(!first) {
					ret.append(", ");
				}
				first = false;
				ret.append(ts(t));
			}
			ret.append("}");
			return ret.toString();
		}
		private static <T> String ts(Iterable<T> iter) {
			StringBuilder ret = new StringBuilder();
			ret.append("{");
			boolean first = true;
			for(T t: iter) {
				if(!first) {
					ret.append(", ");
				}
				first = false;
				ret.append(ts(t));
			}
			ret.append("}");
			return ret.toString();
		}
		public static void dbg(Object... o) throws Exception {
			if(LOCAL) {
				PrintStream ps = new PrintStream("src/Debug.txt");
				System.setErr(ps);
				System.err.print("Line #"+Thread.currentThread().getStackTrace()[2].getLineNumber()+": [");
				for(int i = 0; i<o.length; i++) {
					if(i!=0) {
						System.err.print(", ");
					}
					System.err.print(ts(o[i]));
				}
				System.err.println("]");
			}
		}
	}

}
