赛时考虑怎么维护后面第一个可换位置的时候想到了权值树状数组加二分。赛时没发现权值树状数组加二分是平衡树，傻乎乎的开始敲了，而且由于当时脑抽，算复杂度的时候忘了把树状数组的 $\log$ 算进去，一直以为是单 $\log$ 的，敲完大样例过了，赛后发现自己傻乎乎写了个双 $\log$ 平衡树，跑满了话 $4e8$，祈求别被卡掉。尝试用 $set$ 复现赛时写法，写挂了，大样例都没过，分数下来后还好 AC 了，不然就要去买后悔药了。赛时被刺激一下就能写出来加上快读快写 $203$ 行双 $log$ 平衡树，DeBug 一次就，只改了一个小地方就过了，赛后用 set 写挂了，看来还是紧张环境刺激发挥。。。

贪心思路是考虑每个位置能和后边换就换，如果只有一个能换就换能换的，如果都能换，优先换连通块结束点早的，这样了话即便当前换法不优，在未来某一时刻有机会重换成优的。

#include<bits/stdc++.h>
using namespace std;
template<typename T>
void read(T &x){
	x = 0;char ch = getchar();int f = 1;
	while(!isdigit(ch)){if(ch=='-'){f = -1;}ch = getchar();}
	while(isdigit(ch)){x = x*10+ch-'0';ch = getchar();}
	x*=f;
}
template<typename T>
void print(const T &x){
	if(x>9)print(x/10);
	putchar(x%10|0x30);
}
template<typename T>
void println(const T &x){
	if(x<0){putchar('-');print(-x);
	}else{print(x);}
	putchar('\n');
}
template<typename T>
void printcs(const T &x){
	if(x<0){putchar('-');print(-x);
	}else{print(x);}
	putchar(' ');
}

const int N = 1e5+10;
int t,n,idx,coa[N],cob[N],as[N],bs[N];

int queryT(int x,const vector<int> &tmp){
	if(x==0)return 0;
	int res = 0;
	while(x){
		res+=tmp[x];
		x-=x&-x;
	}
	return res;
}

void add(int x,int v,vector<int> &tmp){
	while(x<tmp.size()){
		tmp[x]+=v;
		x+=x&-x;
	}
}
int query(int l,int r,const vector<int> &tmp){
	return queryT(r,tmp)-queryT(l-1,tmp);
}

char a[N],b[N],ta[N],tb[N];

int find0(int l,const vector<int> &tmp){
	int r = n,mid;
	while(l<r){
		mid = l+r>>1;
		if(query(l,mid,tmp)<mid-l+1){
			r = mid;
		}else{
			l = mid+1;
		}
	}
	return l;
}
int find1(int l,const vector<int> &tmp){
	if(query(l,l,tmp)==1)return l;
	int r = n,mid;
	while(l<r){
		mid = l+r>>1;
		if(query(l,mid,tmp)!=0){
			r = mid;
		}else{
			l = mid+1;
		}
	}
	return l;
}
int main(){
 	freopen("edit.in","r",stdin);
 	freopen("edit.out","w",stdout);
	read(t); 
	while(t--){
		read(n);
		idx  = 0;
		for(int i = 0;i<=n+3;i++){
			as[i] = bs[i] = n+1;
			coa[i] = cob[i] = 0;
		}
		vector<int> ca(n+3,0);
		vector<int> cb(n+3,0);
		scanf("%s",a+1);
		scanf("%s",b+1);
		scanf("%s",ta+1);
		scanf("%s",tb+1);
		ta[0] = '0';tb[0] = '0';ta[n+1] = '0';tb[n+1] = '0';
		for(int i = n;i>=1;i--){
			if(ta[i]=='0')as[i] = i;
			else as[i] = as[i+1];
			if(tb[i]=='0')bs[i] = i;
			else bs[i] = bs[i+1];
		}
		for(int i = 1;i<=n;i++){
			if(ta[i]=='1'&&ta[i-1]=='0'){
				coa[i]=++idx;
			}else if(ta[i]=='1'&&ta[i-1]=='1'){
				coa[i] = coa[i-1];
			}
			if(tb[i]=='1'&&tb[i-1]=='0'){
				cob[i]=++idx;
			}else if(tb[i]=='1'&&tb[i-1]=='1'){
				cob[i] = cob[i-1];
			}
			if(a[i]=='1')add(i,1,ca);
			if(b[i]=='1')add(i,1,cb);
		}
		for(int i = 1;i<=n;i++){
			if(a[i]==b[i])continue;
			if(ta[i]=='1'&&tb[i]=='1'){
				if(as[i]<bs[i]){
					if(b[i]=='0'){
						int p = find0(i+1,ca);
						if(coa[i]==coa[p]&&a[p]=='0'){
							add(i,-1,ca);
							add(p,1,ca);
							swap(a[i],a[p]);
							continue;
						}
					}else{
						int p = find1(i+1,ca);
						if(coa[i]==coa[p]&&a[p]=='1'){
							add(i,1,ca);
							add(p,-1,ca);
							swap(a[i],a[p]);
							continue;
						}
					}
					goto swb;
				}else{
					if(a[i]=='0'){
						int p = find0(i+1,cb);
						if(cob[i]==cob[p]&&b[p]=='0'){
							add(i,-1,cb);
							add(p,1,cb);
							swap(b[i],b[p]);
							continue;
						}
					}else{
						int p = find1(i+1,cb);
						if(cob[i]==cob[p]&&b[p]=='1'){
							add(i,1,cb);
							add(p,-1,cb);
							swap(b[i],b[p]);
							continue;
						}
					}
					goto swa;
				}
			}else if(ta[i]=='1'){
				swa:;
				if(b[i]=='0'){
					int p = find0(i+1,ca);
					if(coa[i]==coa[p]&&a[p]=='0'){
						add(i,-1,ca);
						add(p,1,ca);
						swap(a[i],a[p]);
					}
				}else{
					int p = find1(i+1,ca);
					if(coa[i]==coa[p]&&a[p]=='1'){
						add(i,1,ca);
						add(p,-1,ca);
						swap(a[i],a[p]);
					}
				}
			}else if(tb[i]=='1'){
				swb:;
				if(a[i]=='0'){
					int p = find0(i+1,cb);
					if(cob[i]==cob[p]&&b[p]=='0'){
						add(i,-1,cb);
						add(p,1,cb);
						swap(b[i],b[p]);
					}
				}else{
					int p = find1(i+1,cb);
					if(cob[i]==cob[p]&&b[p]=='1'){
						add(i,1,cb);
						add(p,-1,cb);
						swap(b[i],b[p]);
					}
				}
			}
		}
		int ans = 0;
		for(int i = 1;i<=n;i++){
			if(a[i]==b[i]){
				ans++;
			}
		}
		println(ans);
	}
	return 0;
}