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.
#include <bits/stdc++.h>
#include <ext/numeric>

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef tree<int, null_type, less<int>, rb_tree_tag,
		tree_order_statistics_node_update> ordered_set;
using namespace std;
#define go ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long
typedef vector<vector<int>> vvi;
typedef complex<long double> Point;
const double Pi = acos(-1.0), eps = 1e-8;
#define S second
#define F first
#define X real()
#define Y imag()
#define Angle(v) (atan2((v).Y , (v).X))
#define Length(v) ((long double)hypot((v).Y , (v).X))
#define Lengthsqr(v) (dot((v) , (v)))
const int mxn = 4e2 + 5, mod = 1e9 + 7, MOD = 1e9 + 7, mod2 = 998244353;


void bingo() {
	int n;
	cin>>n;
	string s1 , s2;
	cin>>s1>>s2;
	ll out = 0;
	int curr_mex = 0;
	bool one = true;
	for(int i = 0; i < n; i++){
		int a = s1[i] - '0' , b = s2[i] - '0';
		if(a + b == 1){
			out += 2;
			curr_mex = 0;
			one = false;
		}
		else if(!(a + b)){
			if(curr_mex)
				++out;
			if(one){
				one = false;
				out += 2;
				curr_mex = 0;
				continue;
			}
			curr_mex = 1;

		}
		else {
			if(curr_mex == 1){
				out += 2;
			}else{
				one = true;
			}
			curr_mex = 0;
		}
	}
	out+=curr_mex;
	cout<<out<<'\n';
//	int n, m;
//	cin>>n>>m;
//	vector<array<int,2>>vi(n);
//	for(int i = 0; i < n; i++){
//		cin>>vi[i][0];
//		vi[i][1] = -(i + 1);
//	}
//	sort(vi.begin() , vi.end());
//	vector<int>v(n + 1);
//	for(int i = 0; i < n ; i++){
//		v[-vi[i][1]] =
//	}
//	set<int>st;
//	ll out = 0;
//	for(int i = 0; i < n;i++){
//		int curr = -vi[i][1];
//		int idx = *st.upper_bound(curr);
//		--idx;
//		out += idx + 1;
//		st.insert(vi[i][1]);
//	}
//	cout<<out<<'\n';
}

int main() {
	go
#ifdef LOCAL
	freopen("input.in", "rt", stdin);
//	freopen("output.out", "wt", stdout);
#endif
	//freopen("card.in", "rt", stdin);
	int t = 1;
	cin>>t;
	while (t--) {
		bingo();
	}
	return 0;
}
