考场一个小时切不出来T1于是暴力及时止损，看题解才想到的贪心，，

首先我们要知道，对任意数列进行有限次邻项交换后，必定能得到该数列的全排列。这样你就拿到了 $n\leq10$ 的20分。

如果你能想到在 $t_1$ 和 $t_2$ 中的由连续的1组成的连通块内，对应的 $s_1$ 与 $s_2$ 的部分可以任意排列，那你就拿到了 $t_1=t_2$ 的20分。

如果你能想到当 $s_1$ 全是0或1的时候不管 $s_2$ 如何排列答案都不会变，那你就拿到了性质A的20分。

（性质C太难了不讨论了）（）（）

暴力的60分该拿还是得拿的）

然后是正解

从前往后扫，如果这个位置 $s_1$ 和 $s_2$ 有一个不能能换，那就从对应连通块内挑一个数放上去配对就好了

如果都能换，同上，挑0挑1都一样

如果都不能换，直接算答案

感性地贪一下，如果这个位置不配对，那就是给后面的位置留了一个0或1，但这个数在后面至多也只有1的贡献，还不如拿到就马上配了（

换之前记得先看看这个块剩下的0和1数量还够不够

（其实用并查集维护会方便一点）

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&(-x))
#define mem(a,b) memset(a,b,sizeof a)
#define rev(x) reverse(x.begin(),x.end())
using namespace std;
struct node{
	int n0,n1;
	node operator+(const node&q)const{return (node){n0+q.n0,n1+q.n1};}
}siz[100010][2];
int fa[100010][2];
inline int find(int x,int p){
	if(x==fa[x][p]) return x;
	return fa[x][p]=find(fa[x][p],p);
}
inline void merge(int x,int y,int p){
	x=find(x,p),y=find(y,p);
	if(x!=y) siz[y][p]=siz[y][p]+siz[x][p],fa[x][p]=y;
}
int main(){
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		string s1,s2,t1,t2;cin>>s1>>s2>>t1>>t2;
		for(int i=0;i<n;i++) fa[i][0]=fa[i][1]=i;
		for(int i=0;i<n;i++){
			siz[i][0].n0=s1[i]=='0';
			siz[i][0].n1=s1[i]=='1';
			siz[i][1].n0=s2[i]=='0';
			siz[i][1].n1=s2[i]=='1';
		}
		for(int i=1;i<n;i++){
			if(t1[i]=='1'&&t1[i-1]=='1') merge(i-1,i,0);
			if(t2[i]=='1'&&t2[i-1]=='1') merge(i-1,i,1);
		}
		

		int ans=0;
		for(int i=0;i<n;i++){
			int p1=find(i,0);
			int p2=find(i,1);
			if(siz[p1][0].n0>0&&siz[p2][1].n0>0) siz[p1][0].n0--,siz[p2][1].n0--,ans++;
			else if(siz[p1][0].n1>0&&siz[p2][1].n1>0) siz[p1][0].n1--,siz[p2][1].n1--,ans++;
		}
		cout<<ans<<endl;
	}
	
	
	return 0;
}