#include<iostream>   
#include<cstdio> 
#include<set> 
#include<queue> 
#define N (int)1e5+5 
using namespace std ;     
int T,n,ans;  
bool a[N],b[N],va[N],vb[N]; 
int sa[N],sb[N],sz[N];  
int pa,pb,ta,tb,l=-1,r=-1; 
char ch; 
struct node{
	int l,r,sum1,sum0;
}ka[N],kb[N]; 
int fa[N],fb[N];    
bool flag;
priority_queue<pair<int,pair<int,int> > > q; 
int main(){
	ios::sync_with_stdio(false);  
	freopen("edit.in","r",stdin); 
	freopen("edit.out","w",stdout);
	cin>>T; 
	while(T--){ 
		ans=0;
		cin>>n;  
		flag=true;
		for(int i=1;i<=n;i++){
			cin>>ch; 
			a[i]=ch-'0'; 
			sa[i]=a[i]+sa[i-1]; 
		}  
		for(int i=1;i<=n;i++){
			cin>>ch; 
			b[i]=ch-'0'; 
			sb[i]=b[i]+sb[i-1];  
			sz[i]=sz[i-1]+(a[i]==b[i]); 
		}
		for(int i=1;i<=n;i++){
			cin>>ch; 
			va[i]=ch-'0';   
			if(va[i]==1&&va[i-1]==0) 
				pa=i; 
			if(va[i-2]==0&&va[i]==0) 
				va[i-1]=0; 
			if(va[i]==0&&va[i-1]==1)
				ka[++ta]={pa,i-1,sa[i-1]-sa[pa-1],i-pa-(sa[i-1]-sa[pa-1])};   
			fa[i]=ta+1; 
		}   
		if(va[n]&&!va[n-1])va[n]=0;
		if(va[n]==va[n-1]&&va[n]==1)
			ka[++ta]={pa,n,sa[n]-sa[pa-1],n-pa+1-(sa[n]-sa[pa-1])}; 
		for(int i=1;i<=n;i++){
			cin>>ch; 
			vb[i]=ch-'0';  
			if(vb[i]==1&&vb[i-1]==0) 
				pb=i; 
			if(vb[i-2]==0&&vb[i]==0) 
				vb[i-1]=0;  
			if(vb[i]==0&&vb[i-1]==1)
				kb[++tb]={pb,i-1,sb[i-1]-sb[pb-1],i-pb-(sb[i-1]-sb[pb-1])};    
			fb[i]=tb+1; 
		}         
		if(vb[n]&&!vb[n-1])vb[n]=0; 
		if(vb[n]==vb[n-1]&&vb[n]==1)
			kb[++tb]={pb,n,sb[n]-sb[pb-1],n-pb+1-(sb[n]-sb[pb-1])};
		for(int i=1;i<=n;i++){
			if(va[i]!=vb[i]){
				flag=false;
				break;
			}
		}
		l=1;
		ta=va[1]; 
		tb=vb[1]; 
		if(sa[n]==n){
			cout<<sb[n]<<endl; 
			continue;
		} 
		if(sa[n]==0){
			cout<<n-sb[n]<<endl; 
			continue;
		} 
		for(int i=2;i<=n;i++){
			if(va[i]!=ta||vb[i]!=tb){
				q.push(make_pair(-ta-tb,make_pair(l,i-1))); 
				ta=va[i]; 
				tb=vb[i];
				l=i;
			} 
		}     
		q.push(make_pair(-ta-tb,make_pair(l,n)));  
		if(flag){
			while(!q.empty()){ 
				int opt=q.top().first,l=q.top().second.first,r=q.top().second.second; 
				int len=r-l+1;  
				q.pop();
				if(opt==0) 
					ans+=sz[r]-sz[l-1];  
				else{
					ans+=min(ka[fa[l]].sum0,kb[fb[l]].sum0)+min(ka[fa[l]].sum1,kb[fb[l]].sum1); 
				}
			} 
			cout<<ans<<endl; 
			continue;
		}
		while(!q.empty()){
			int opt=q.top().first,l=q.top().second.first,r=q.top().second.second; 
			int len=r-l+1;   
			q.pop(); 
			if(opt==0)
				ans+=sz[r]-sz[l-1];
			if(opt==-1){   
				if(va[l]){
					int sum1=sb[r]-sb[l-1],sum0=len-(sb[r]-sb[l-1]); 
					if(ka[fa[l]].sum1>=sum1&&ka[fa[l]].sum0>=sum0){
						ans+=len; 
						ka[fa[l]].sum1-=sum1; 
						ka[fa[l]].sum0-=sum0;
					} 
					else if(ka[fa[l]].sum1>=sum1&&ka[fa[l]].sum0<sum0){
						ans+=sum1+ka[fa[l]].sum0; 
						ka[fa[l]].sum1-=(len-ka[fa[l]].sum0); 
						ka[fa[l]].sum0=0;
					} 
					else if(ka[fa[l]].sum0>=sum0&&ka[fa[l]].sum1<sum1){
						ans+=sum0+ka[fa[l]].sum1; 
						ka[fa[l]].sum1=0; 
						ka[fa[l]].sum0-=(len-ka[fa[l]].sum1);
					} 
				} 
				if(vb[l]){ 
					int sum1=sa[r]-sa[l-1],sum0=len-(sa[r]-sa[l-1]); 
					if(kb[fb[l]].sum1>=sum1&&kb[fb[l]].sum0>sum0){
						ans+=len; 
						kb[fb[l]].sum1-=sum1; 
						kb[fb[l]].sum0-=sum0;
					} 
					else if(kb[fb[l]].sum1>=sum1&&kb[fb[l]].sum0<=sum0){
						ans+=sum1+kb[fb[l]].sum0; 
						kb[fb[l]].sum1-=(len-kb[fb[l]].sum0); 
						kb[fb[l]].sum0=0;
					} 
					else if(kb[fa[l]].sum0>=sum0&&kb[fb[l]].sum1<=sum1){
						ans+=sum0+kb[fb[l]].sum1; 
						kb[fb[l]].sum1=0; 
						kb[fb[l]].sum0-=(len-kb[fb[l]].sum1);
					} 
				}
			} 
			else{  
				int p=min(ka[fa[l]].sum0,kb[fb[l]].sum0);
				if(p>len){
					ka[fa[l]].sum0-=len; 
					kb[fb[l]].sum0-=len; 
					ans+=len;
				} 
				else{
					len-=p; 
					ka[fa[l]].sum0-=p; 
					kb[fb[l]].sum0-=p; 
					ans+=p; 
					int q=min(ka[fa[l]].sum1,kb[fb[l]].sum1); 
					if(q>len){
						ka[fa[l]].sum1-=len; 
						kb[fb[l]].sum1-=len; 
						ans+=len; 
					} 
					else{
						ka[fa[l]].sum1-=q; 
						kb[fb[l]].sum1-=q; 
						ans+=q; 
					}
				}
			} 
		} 
		cout<<ans<<endl; 
	}
	return 0;
} 
