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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.AbstractMap;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.*;
import java.io.*;

// Java Template Pramod Hosahalli...
public class Solution {

	//static FastReader in = new FastReader();
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static int mod = 1000000007;

	private static void go() throws Exception {
		int n = pi(in.readLine());
		char[] ch1 = in.readLine().toCharArray();
		char[] ch2 = in.readLine().toCharArray();
		
		Map<Integer,Integer[]> map1 = new HashMap<>();
		Map<Integer,Integer[]> map2 = new HashMap<>();

		int z = Integer.MAX_VALUE;
		int o = Integer.MAX_VALUE;
		
		for(int i = n-1; i>=0; i--){
			if(ch1[i] == '0') z = i;
			else o = i;
			map1.put(i, new Integer[]{z, o});
		}

		z = Integer.MAX_VALUE;
		o = Integer.MAX_VALUE;
		
		for(int i = n-1; i>=0; i--){
			if(ch2[i] == '0') z = i;
			else o = i;
			map2.put(i, new Integer[]{z, o});
		}

		int i = 0;
		int sum = 0;
		while(i < n){
			if(ch1[i]!=ch2[i]) sum+=2;
			else{
				if(ch1[i] == ch2[i] && ch1[i] == '0') sum+=1;
				else{
					int index = Math.min(map1.get(i)[0], map2.get(i)[0]);
					if(index == Integer.MAX_VALUE && i > 0) sum++;

					if(index!= Integer.MAX_VALUE){
						i = index;
						sum+=2;
					}
					if(i == Integer.MAX_VALUE)break;
				}
			}
			i++;
		}
		print(1, sum+"");
	}

	public static void main(String[] args) throws Exception {
		int t = pi(in.readLine());
		while(t-- > 0){
			go();
		}
		in.close();
	}

	static long mul(long a, long b) {
		return ((a % mod) * (b % mod)) % mod;
	}

	static class FastReader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public FastReader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public FastReader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public int[] readIntArray(int n) throws IOException{
			int[] fx = new int[n];
			for(int i = 0; i < n; i++) fx[i] = ni();
			return fx;
		}

		public long[] readLongArray(int n) throws IOException {
			long[] fx = new long[n];
			for(int i = 0; i < n; i++) fx[i] = nl();
			return fx;
		}

		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 ni() 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 nl() 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 nd() 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();
		}
	}

	static String rl() throws Exception{
		return in.readLine();
	}

	static int pi(String s) {
		return Integer.parseInt(s);
	}

	static long pl(String s) {
		return Long.parseLong(s);
	}

	static void print(int newline, String s) {
		System.out.print(s);
		if (newline != 0) System.out.println();
		// System.out.flush();
	}

	static void print(int newline, int[] arr) {
		StringBuilder sb = new StringBuilder("");
		for(int x : arr) sb.append(x+" ");
		System.out.print(sb.toString().trim());
		if (newline != 0) System.out.println();
		// System.out.flush();
	}

	static void cprint(int x) {
		print(0, "Case #" + x + ": ");
	}

	//utility function for gcd
	private static long gcd(long a, long b)
	{
		if(a == 0 || b == 0)return a + b;
		if(a > b)return gcd(a % b, b);
		return gcd(a, b % a);
	}

	// construct sparse table : for static range queries
	static class SparseTable{
		static long[][] precompute(long[] arr)
		{
			int n = arr.length;
			int p = (int)((double)Math.log(n) / Math.log(2));
			long[][] f = new long[p+1][n];

			for(int i = 0; i < n; i++) f[0][i] = arr[i];
			for(int j = 1; j <= p; j++){
				for(int i = 0; i + (1 << j) - 1 < n; i++){
					f[j][i] = gcd(f[j-1][i], f[j-1][i + (1 << (j-1))]);
				}
			}
			return f;
		}
	}

	//Union Rank Algorithm
	static class UnionFind {
		int[] parent = null;
		int[] rank = null;

		UnionFind(int n){
			parent = new int[n];
			rank = new int[n];
			for(int i = 0; i < n; i++) parent[i] = i;
		}

		int find(int v){
			if(parent[v] != v) parent[v] = find(parent[v]);
			return parent[v];
		}

		boolean union(int x, int y) {
			int u = find(x);
			int v = find(y);

			//both belong to same set...
			if(u == v)return false;

			if(rank[u] > rank[v])
				parent[v] = u;
			else if(rank[u] < rank[v])
				parent[u] = v;
			else{
				parent[u] = v;
				rank[v]++;
			}
			return true;
		}
	}

	//Fenwick Tree Implementation
	static class BIT{
		int bit[] = null;

		BIT(int n){
			bit = new int[n+1];
		}

		private void update(int x){
			int index = x;
			while(index < bit.length){
				bit[index]+=1;
				index += (index & -index);
			}
		}

		private int sum(int l){
			int index = l-1;
			int c = 0;
			while(index > 0){
				c+=bit[index];
				index -= (index & -index);
			}
			return c;
		}
	}

	//Suffix Array Impl
	static class SuffixArray{

		// suffix array in O(n*log^2(n))
		public static Integer[] suffixArray(CharSequence s) {
			int n = s.length();
			Integer[] sa = new Integer[n];
			int[] rank = new int[n];
			for (int i = 0; i < n; i++) {
				sa[i] = i;
				rank[i] = s.charAt(i);
			}
			for (int len = 1; len < n; len *= 2) {
				long[] rank2 = new long[n];
				for (int i = 0; i < n; i++)
					rank2[i] = ((long) rank[i] << 32) + (i + len < n ? rank[i + len] + 1 : 0);

				Arrays.sort(sa, (a, b) -> Long.compare(rank2[a], rank2[b]));

				for (int i = 0; i < n; i++)
					rank[sa[i]] = i > 0 && rank2[sa[i - 1]] == rank2[sa[i]] ? rank[sa[i - 1]] : i;
			}
			return sa;
		}
	}

}