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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;

public class Practice {
	public static long mod = (long) Math.pow(10, 9) + 7;
	public static long mod2 = 998244353;
//	public static int tt = 1;
	public static ArrayList<Long> one;
	public static ArrayList<Long> two;
//	public static long[] fac = new long[200005];
//	public static long[] invfac = new long[200005];

	public static void main(String[] args) throws Exception {
		PrintWriter pw = new PrintWriter(System.out);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());

		while (t-- > 0) {
			int n = Integer.valueOf(br.readLine());
			String str1 = br.readLine();
			String str2 = br.readLine();
			int ans = 0;
			for (int i = 0; i < n; i++) {
				if (str1.charAt(i) != str2.charAt(i)) {
					ans += 2;
				} else {
					if (str1.charAt(i) == '1') {
						if (i != n - 1) {
							if (str1.charAt(i + 1) == '0' || str2.charAt(i + 1) == '0') {
								ans += 2;
								i++;
							}
						}
					} else {
						if (i != n - 1 && (str1.charAt(i + 1) == '1' || str2.charAt(i + 1) == '1')) {

							ans += 2;
							i++;

						} else {
							ans += 1;
						}
					}
				}
			}
			pw.println(ans);
		}

		pw.close();
	}

// private static int kmp(String str) {
//		// TODO Auto-generated method stub
//		// System.out.println(str);
//		int[] pi = new int[str.length()];
//		pi[0] = 0;
//		for (int i = 1; i < str.length(); i++) {
//			int j = pi[i - 1];
//			while (j > 0 && str.charAt(i) != str.charAt(j)) {
//				j = pi[j - 1];
//			}
//			if (str.charAt(j) == str.charAt(i)) {
//				j++;
//			}
//			pi[i] = j;
//			System.out.print(pi[i]);
//		}
//		System.out.println();
//		return pi[str.length() - 1];
//	}

}

//	private static void getFac(long n, PrintWriter pw) {
//		// TODO Auto-generated method stub
//		int a = 0;
//		while (n % 2 == 0) {
//			a++;
//			n = n / 2;
//		}
//		if (n == 1) {
//			a--;
//		}
//		for (int i = 3; i <= Math.sqrt(n); i += 2) {
//			while (n % i == 0) {
//				n = n / i;
//				a++;
//			}
//		}
//		if (n > 1) {
//			a++;
//		}
//		if (a % 2 == 0) {
//			pw.println("Bob");
//		} else {
//			pw.println("Alice");
//		}
//		//System.out.println(a);
//		return;
//	}

//	private static long power(long a, long p) {
//		// TODO Auto-generated method stub
//		long res = 1;
//		while (p > 0) {
//			if (p % 2 == 1) {
//				res = (res * a) % mod;
//			}
//			p = p / 2;
//			a = (a * a) % mod;
//		}
//		return res;
//	}
//
//	private static void fac() {
//		fac[0] = 1;
//		// TODO Auto-generated method stub
//		for (int i = 1; i < fac.length; i++) {
//			if (i == 1) {
//				fac[i] = 1;
//			} else {
//				fac[i] = i * fac[i - 1];
//			}
//			if (fac[i] > mod) {
//				fac[i] = fac[i] % mod;
//			}
//		}
//	}
//
//	private static int getLower(Long long1, Long[] st) {
//		// TODO Auto-generated method stub
//		int left = 0, right = st.length - 1;
//		int ans = -1;
//		while (left <= right) {
//			int mid = (left + right) / 2;
//			if (st[mid] <= long1) {
//				ans = mid;
//				left = mid + 1;
//			} else {
//				right = mid - 1;
//			}
//		}
//		return ans;
//	}

//private static long getGCD(long l, long m) {
//
//	long t1 = Math.min(l, m);
//	long t2 = Math.max(l, m);
//	if (t1 == 0) {
//		return t2;
//	}
//	while (true) {
//		long temp = t2 % t1;
//		if (temp == 0) {
//			return t1;
//		}
//		t2 = t1;
//		t1 = temp;
//	}
//}